Course Details
Subject {L-T-P / C} : MA4402 : Finite Automata and Formal Languages { 3-1-0 / 4}
Subject Nature : Theory
Coordinator : Kamalesh Acharya
Syllabus
| Module 1 : |
Deterministic Finite Automata (DFA), Input alphabet, Extended transition function, Language of DFA, Building DFA, Examples. NFA (Nondeterministic Finite Automata), Language of a NFA, Equivalence of DFAs and NFAs, Subset Construction, epsilon-NFA, Extended transition function of epsilon –NFA, Language of epsilon –NFA, epsilon -NFA to NFA, epsilon -NFA to DFA |
| Module 2 : |
Definition of Regular expression, Equivalence of epsilon -NFA and regular expression, DFA to Regular expression, Closure properties of Regular Set, Substitution, Pumping Lemma, Arden’s Theorem, Minimization of FA, Two way FA, Finite automata with output, Equivalence of Moore and Mealy machine.
|
| Module 3 : |
Context free grammars (CFG), Context free language (CFL), Derivation Tree/Parse Tree, Leftmost and Rightmost derivations, Ambiguity in CFG, Algorithms to construct reduced grammar, Elimination of Null and Unit productions, Chomsky Normal Form (CNF), Greibach Normal Form (GNF)
|
| Module 4 : |
Definition of Pushdown Automata (PDA), Language accepted by PDA, Deterministic PDA, Equivalence PDA, Equivalence PDA and CFL, Relationship between regular language and CFL, Pumping lemma for CFLs, Closer properties of CFLs. Definition of Turning Machine, Language accepted by a Turning machine, Minimization of finite state machine. |
Course Objective
| 1 . |
To identify the hierarchy of problems arising in computer science. |
| 2 . |
To accept a set of strings of a language and to design finite automata. |
| 3 . |
To generate strings from a context free language and to design context free grammars. |
| 4 . |
To develop a formal notation for strings, languages and machines. |
Course Outcome
| 1 . |
CO1. To use basic concepts of formal languages of finite automata techniques.
|
| 2 . |
CO2. To Design Finite Automata’s for different Regular Expressions and Languages.
|
| 3 . |
CO3 Understand the equivalence between Context-Free Grammars and Pushdown automata.
|
| 4 . |
CO4 To solve various problems of applying normal form techniques, push down automata and
|
Essential Reading
| 1 . |
E. J. Hopcroft, D. J. Ullman and R. Motwani, Introduction to Automata Theory, Languages and Computation,, Pearson Education , 3rd ed.,, 2007. |
| 2 . |
P. Linz,, An Introduction to Formal Languages and Automata,, Jones & Bartlett Learning, , 1st Indian edition, 2017 |
Supplementary Reading
| 1 . |
C.J. Martin, Introduction to Languages and the Theory of Computation,, McGraw-Hill Higher Education, , 4th ed., 2011 |
| 2 . |
M. Sipser,, Introduction to the Theory of Computation,, Cengage Learning, , 3rd ed., 2013. |
Journal and Conferences
| 1 . |
NA |