Code  CS 302  
Term  201801  
Title  Formal Languages and Automata Theory  
Faculty  Faculty of Engineering and Natural Sciences  
Subject  Computer Sci.& Eng.(CS)  
SU Credit  3  
ECTS Credit  6.00 / 6.00 ECTS (for students admitted in the 201314 Academic Year or following years)  
Instructor(s)  Kemal ?nan inan@sabanciuniv.edu,  
Language of Instruction  English  
Level of Course  Undergraduate  
Type of Course  Click here to view.  


Prerequisites (only for SU students) 
  
Mode of Delivery  Formal lecture,Interactive lecture  
Planned Learning Activities  Interactive,Learner centered,Communicative  
Content 
Introduction to languages, grammars and computation, Chomsky hierarchy, Regular languages and regular expressions, finite state automata and nondeterminism, automata determinization and minimization, pumping lemma and closure properties for regular languages, context free languages and grammars, push down automata, pumping lemma for contextfree languages, closure properties of contextfree languages. 

Objective 
To introduce finite state machines , contex free grammars and Turing Machines (only on an introductory level) and their properties as the basis for the formal expressivity of computer languages and present algorithms and their computational complexity for solving linguistic decision problems . 

Learning Outcome 
Construct deterministic and nondeterministic finite state automata (DFA and NFA) for solving simple decision problems and perform conversions from nondeterministic to deterministic finite automata as well as between regular expressions and finite state automata. Evaluate the computational complexity of algorithms involved in the decision problems of finite state automata, use the pumping lemma to demonstrate the nonregularity of languages 

Programme Outcomes  


Update User:  
Update Date: 
Assessment Methods and Criteria  
Percentage (%)  
Final  35 
Midterm  20 
Exam  35 
Assignment  10 
Recommended or Required Reading  
Textbook 
MAIN TEXT: Introduction to Automata Theory, Languages and Computation , Hopcroft, Motwani & Ullman, Pearson (Addison Wesley) 2006 , 3rd edition 
Readings 
AUXILIARY TEXT : Elements of the Theory of Computation, Lewis & Papadimitrious, Prentice Hall 1998 (out of print and discontinued) 