AI-Powered Learning Platform

Subject Syllabus

AL-601 - Theory of Computation

AIML · Semester 6

Course Modules

Learn topic-wise with Hyper AI and revise using mapped PYQs.

Examples of automata machines Finite Automata as a language acceptor and translator Moore machines and mealy machines Composite machine Conversion from Mealy to Moore and vice versa

Non Deterministic Finite Automata (NDFA)Deterministic finite automata machines Conversion of NDFA to DFA Minimization of automata machines Regular expression Arden's theorem Meaning of union, intersection, concatenation and closure 2 way DFA

Types of grammar Context sensitive grammar Context free grammar Regular grammar Derivation trees Ambiguity in grammar Simplification of context free grammar Conversion of grammar to automata machine and vice versa Chomsky hierarchy of grammar Killing null and unit productions Chomsky normal form and Greibach normal form

Example of PDA Deterministic and non-deterministic PDA Conversion of PDA into context free grammar and vice versa CFG equivalent to PDA Petrinet model

Techniques for construction Universal Turing machine Multitape, multihead and multidimensional Turing machine N-P complete problems Decidability and Recursively Enumerable Languages Decidability, decidable languages, undecidable languages Halting problem of Turing machine The post correspondence problem