Unit 1
Automata and Languages: Chomsky hierarchy of languages, Introduction Finite Automata – Regular Expressions – Nondeterministic Finite Automata – equivalence of NFAs and DFAs – Minimization of DFA.
| Course Name | Theory of Computation |
| Course Code | 15CSE303 |
| Program | B. Tech. in Computer Science and Engineering |
| Semester | Five |
| Year Taught | 2019 |
Automata and Languages: Chomsky hierarchy of languages, Introduction Finite Automata – Regular Expressions – Nondeterministic Finite Automata – equivalence of NFAs and DFAs – Minimization of DFA.
Regular Expressions – Non-Regular Languages – Pumping Lemma for regular languages.
Parse tree derivations (top-down and bottom-up) Context free languages – Chomsky normal form, GNF – Push Down Automata – Pumping lemma for context free language. CYK Algorithm, Deterministic CFLs. Ambiguous grammar, removing ambiguity, Computability Theory: Turing Machines – Non-deterministic Turing Machines – CSG, Undecidability – PCP Computation histories – Reducibility.
DISCLAIMER: The appearance of external links on this web site does not constitute endorsement by the School of Biotechnology/Amrita Vishwa Vidyapeetham or the information, products or services contained therein. For other than authorized activities, the Amrita Vishwa Vidyapeetham does not exercise any editorial control over the information you may find at these locations. These links are provided consistent with the stated purpose of this web site.