Theory of Computation Syllabus — Government College of Engineering an…
Full syllabus, topics and curated resources for Theory of Computation (Government College of Engineering and Technology, Jammu).
Formal languages, automata theory, and computability using Turing machines
- Subject code: CST-3504
- University: Government College of Engineering and Technology, Jammu
- Course: BE (2022 onwards)
- Branch: CE
- Semester: 5
Theory of Computation syllabus
Unit 1: Introduction to Formal Languages and Automata
- Symbols and String Concatenation
- Alphabet and Language
- Tree Representation
- Mathematical Induction Proofs
- States and Transition Tables
- Finite Automata (Introduction)
- Regular Expressions (Introduction)
- Pushdown Automata (Introduction)
- Turing Machine (Introduction)
- Context Free Grammars (Introduction)
Unit 2: Finite Automata
- Deterministic Finite Automata (DFA)
- Designing DFA
- Non-Deterministic Finite Automata (NFA) without E-moves
- Conversion of NFA to DFA
- Equivalence of DFA and NFA
- NFA with E-moves
- Regular Expression Designing
- Finite Machine with Output (Introduction)
- Moore Machine
- Mealy Machine
- Conversion and Equivalence of Moore and Mealy Machines
Unit 3: Regular Grammar and Context Free Languages
- Context Free Grammar
- Context Free Languages
- Reduced Form of Grammar
- Ambiguous and Non-Ambiguous Grammar
- Acceptors and Generators
- Relations Between Classes of Languages
- Pumping Lemma of Regular Sets
- Chomsky's Hierarchy of Languages
- Derivation Trees