Why study the Theory of Computation, Languages and Strings: Strings,
Languages. A Language Hierarchy, Computation,
Finite State Machines(FSM): Deterministic FSM, Regular languages, Designing FSM,
Nondeterministic FSMs, From FSMs to Operational Systems, Simulators for
FSMs, Minimizing FSMs, Canonical form of Regular languages, Finite State
Transducers, Bidirectional Transducers.
Regular Expressions (RE): what is a RE?, Kleene’s theorem, Applications of REs, Manipulating and Simplifying REs.
Regular Grammars: Definition,Regular Grammars and Regular languages.
Regular Languages (RL) and Nonregular Languages: How many RLs, To show that a language is regular, Closure properties of RLs, to show some languages are not RLs.
Context-Free Grammars(CFG): Introduction to Rewrite Systems and Grammars, CFGs and languages, designing CFGs, simplifying CFGs, proving that a Grammar is correct, Derivation and Parse trees, Ambiguity, Normal Forms.
Pushdown Automata (PDA): Definition of non-deterministic PDA, Deterministic and Non-deterministic PDAs, Non-determinism and Halting, alternative equivalent definitions of a PDA, alternatives that are not equivalent to PDA.
Context-Free and Non-Context-Free Languages: Where do the Context-Free Languages(CFL) fit, Showing a language is context-free, Pumping theorem for CFL, Important closure properties of CFLs, Deterministic CFLs.
Algorithms and Decision Procedures for CFLs: Decidable questions, Un-decidable questions. Turing Machine: Turing machine model, Representation, Language acceptability by TM, design of TM, Techniques for TM construction.
Variants of Turing Machines (TM), The model of Linear Bounded automata: Decidability: Definition of an algorithm, decidability, decidable languages, Undecidable languages, halting problem of TM, Post correspondence problem.
Complexity: Growth rate of functions, the classes of P and NP,
Quantum Computation: quantum computers, Church-Turing thesis.