• Back
• Video Tutorials
• Slides
• Links

Theory of Computing

• Automata Tutorial
• Review of mathematical background in automata
• Binary relations, Graph and String in automata
• Languages, Proofs, Inductive definitions in automata
• Finite automata
• Deterministic and Non-deterministic Finite automata
• Regular expressions and Regular sets
• Pumping lemma, closure properties
• Kleene’s Theorem
• Regular grammars
• Context Free grammar and languages
• Simplified forms and normal forms
• Useful symbols, productions, unit productions in Forms
• Chomsky normal form
• Push-down automata
• Equivalence between push-down automata and context-free languages
• Introduction to Turing machines