DCRUST SYLLABUS
CSE307C FORMAL LANGUAGES & AUTOMATA THEORY
CATEGORY : ENGINEERING SCIENCE COURSE
Course Objectives:
- To understand the basic properties of formal languages and formal grammars
- To understand the basic properties of deterministic and nondeterministic finite automata
- To understand the basic properties of Turing machines and computing with Turing machines
- To understand the concepts of tractability and decidability, the concepts of NP-completeness and NP-hard problems
Unit I
Basic Computational Constructs : Finite State Systems, Basic Definitions Non-Deterministic finiteautomata (NDFA), Deterministic finite automata (DFA), Equivalence of DFA and NDFA Finite automata with E-moves, Regular Expressions, Equivalence of finite automata and Regular Expressions, Regular expression conversion and vice versa. Conversion of NFA to DFA by Arden’s Method Concept of basic Machine, Properties and limitations of FSM, Moore and Mealy Machines, Equivalence of Moore and Mealy machines.
Click on any topic to read about the topic.
Unit II
Regular Sets& Grammars : The Pumping Lemma for Regular Sets, Applications of the pumping lemma,Closure properties of regular sets, Myhill-Nerode Theorem and minimization of finite Automata, Minimization Algorithm. Definition, Context free and Context sensitive grammar, Ambiguity regular grammar, Reduced forms, Removal of useless Symbols and unit production, Chomsky Normal Form (CNF), Griebach Normal Form (GNF).
Click on any topic to read about the topic.
Unit III
Pushdown Automata &Turing Machines: Introduction to Pushdown Machines, Applications of Pushdown Machines Deterministic and Non-Deterministic Turing Machines, Design of T.M, Halting problem of T.M., Post’s Correspondence Problem.
Click on any topic to read about the topic.
Unit IV
Chomsky Hierarchies & Computability: Chomsky hierarchies of grammars, unrestricted grammars, Context sensitive languages, Relation between languages of classes Primitive Recursive Functions.
Click on any topic to read about the topic.
TEXT /REFERENCE BOOKS:
- Introduction to automata theory, language & computations- Hopcroaft & O.D.Ullman, R Mothwani, Addison Wesley Publishers.
- Theory of Computer Sc.(Automata, Languages and computation):K.L.P.Mishra& N.Chandrasekaran, 2000, PHI.
- Introduction to formal Languages & Automata-Peter Linz, 2001, NarosaPubl.
- Fundamentals of the Theory of Computation- Principles and Practice by RamondGreenlaw and H. James Hoover, 1998, Harcourt India Pvt. Ltd..
- Elements of theory of Computation by H.R. Lewis & C.H. Papaditriou, 1998, PHI.
- Introduction to languages and the Theory of Computation by John C. Martin 2012, T.M.H.
Course Outcomes: After successful completion of the course, a student will be able to :-
- Master regular languages and finite automata.
- Master Context‐free languages, push‐down automata, and Turing recognizable languages.
- Understand the theoretical foundations of computer science.
- Analytically and intuitively solve problems in related areas of theory in computer science.