- General concept of theory of computation
- Motivation of study and applications
- Basic concepts: symbol, alphabet, string/word. Language: Definition, language states, difference between natural and formal language
- Basic machine: concept
- Finite State Machine (FSM): Definition
- Transition graphs, Adjacency matrix, Machine functions and state transition function
- Finite automata (FA) - Definition of deterministic finite Automaton (DFA) and Non-deterministic finite automaton (NFA). Comparison.
- Language accepted by FA. NFA and theorem.
- Regular Expressions: Recursive definition of regular expression. Regular set.
- NFA with e-Moves definitions, NFA with e- moves, NFA without e moves, NFA and Regular expressions
- Regular sets - properties, Pumping lemma
- FA limitations
- Grammars: Definition production rules, derivation trees, ambiguous grammar, removal of ambiguity.
- Reduced form grammar: removal of unit productions, Epsilon production, Chomsky hierarchy
- Context Free Grammar (CFG): simplification, Context Free Language (CFL): definition, inherently ambiguous CFLs
- Regular grammar and finite automata. Normal Forms, Chomsky normal form (CNF), Greibach normal form (GNF).
- Basics of Stack Memory Machines, Pushdown Stack Memory Machine: (PDA).
- Deterministic pushdown automata (DPDA) – Definition. Non Deterministic pushdown automata (NPDA) - definition.
- Relative Powers of DPDA and NPDA, PDA and CFG, closure properties of CFLs
- Production System –Definition and axioms
- Introduction, Definitions, model, comparison of Turing Machine -(TM), FSM, and PDM. Examples of TM, recursively enumerable sets.
- Church's Turing hypothesis, multi stack Turing machine. TM limitations, halting problem
- Incompleteness and undecidability Solvability, Semi-solvability and unsolvability.
- Applications of RE and FA - lexical analyzer, text editor and searching using RE
- Applications of PDA - Expression conversion
- Applications of CFG - syntax analysis, language definition