Formal Language and Automata Theory
Get the full GTU study material, English & Gujarati textbook PDFs, syllabus curriculum, and solved previous year question papers.
English Book & Chapters
English Book Coming Soon
We are working hard to add this material. Stay tuned for updates!
Follow on Instagram for UpdatesGTU Previous Year Papers
Formal Language and Automata Theory Syllabus — Unit-wise Content
The official GTU curriculum for Formal Language and Automata Theory (subject code 3151605) as prescribed for ICT · Semester 5 divides the course into 6 units, covering 41 listed topics. The unit-wise breakdown below is read from the GTU syllabus document for this subject code, so you can check what the course actually covers before deciding which papers to attempt.
Download the official syllabus PDF (3151605)Unit 1 Introduction to Finite Automata
- Introduction to Finite Automata
- Central Concepts of Automata Theory
- Deterministic Finite Automata (DFA)
- Nondeterministic Finite Automata (NFA)
- Finite Automata with Epsilon Transition
Unit 2 Regular Expressions and Languages
- Regular Expressions
- Finite Automata and Regular Expressions
- Applications of Regular Expressions
- Proving Languages Not to Be Regular
- Closure Properties of Regular Languages
- Equivalence and Minimization of Automata – Pumping Lemma
Unit 3 Context Free Grammars and Languages Parse Trees
- Applications of Context Free Grammars
- Ambiguity in Grammars and Languages
- Eliminating Useless Symbols
- Computing the Generating and Reachable Symbols
- Eliminating Epsilon Productions
- Eliminating Unit Productions
- BacosNaur Form (BNF)
- Chomsky Normal Form (CNF)
Unit 4 Pushdown Automata, CFL and NCFL
- Definition of the Pushdown Automaton (PDA)
- The Languages of a PDA, Equivalence of PDA’s and CFG’s
- Deterministic Pushdown Automata
- The Pumping Lemma for Context Free Languages
- Closure Properties of Context Free Languages
- Pumping lemma for CFL, Intersections and Complements of CFL, Non- CFL
Unit 5 Turing Machine (TM)
- Problems That Computers Cannot Solve
- The Subject Code: 3151605 w.e.f
- AY 2018-19 Turing Machine
- Programming Techniques for Turing Machines
- Extensions to the Basic Turing Machine
- Restricted Turing Machines
- Turing Machines and Computers
- Definition of Post’s Correspondence Problem
- A Language That Is Not Recursively Enumerable
- An Undecidable Problem That Is RE, Context sensitive languages and Chomsky hierarchy
- Other Undecidable Problems
Unit 6 Computable Functions
- constant functions
- Primitive Recursive Functions
- Bounded Mineralization
- Regular function
- Recursive Functions
Study on Android App:
