Theory of Machines and Languages
- Introductory Topics (4 sessions)
Propositional logic, deductive logic, proof system, set theory, Russells paradox, countable and uncountable sets, languages ??and grammars.
- Finite State Machines (8 sessions)
Finite deterministic acceptors, non-deterministic acceptors, regular languages, regular expressions, linear right-handed grammars, linear left-handed grammars, regular grammars, linear grammars, irregular languages, pumping lemma for regular languages.
- Context-Free Languages (10 sessions)
Context-free grammars, context-free languages, left-handed derivation, right-handed derivation, derivation tree, ambiguous grammars, ambiguous grammars, inherently ambiguous languages, ambiguous languages, simplification of context-free grammars, Chomsky-natural context-free grammars, Greibach-natural context-free grammars, membership problem, CYK algorithm, pushdown machines, equivalence of pushdown machines and context-free grammars
- Computability (8 sessions)
Turing machine, Church-Turing thesis, decidability and undecidability, computability and uncomputability, halting problem, post assignment problem, computational complexity, P-complexity class, NP-complexity class, NP-complete problems, NP-hard problems.