Automata Languages and Computations is a computer science core paper that revolves around compiler design and how computations are held in a system’s. It gives a complete theoretical picture of how a computer would perform for such problems. Here you have some jots for ALC.
Finite Automata and Regular Expressions: Formal Languages and Regular expressions, Deterministic and Non-Deterministic Finite Automata, Finite Automata with ?-moves, Equivalence of NFA and DFA, Minimization of finite automata, Two-way finite automata, Moore and Mealy machines, Applications of finite automata.
Regular Sets and Context Free Grammars: Properties of regular sets, Context-Free Grammars – Derivation trees, Chomsky Normal Forms and Greibach Normal Forms, Ambiguous and unambiguous grammars.
Pushdown Automata and Parsing Algorithms: Pushdown Automata and Context-Free Languages; Top-down parsing and Bottom-up parsing, Properties of CFL, Applications of Pumping Lemma, Closure properties of CFL and decision algorithms.
Turing machines: Turing machines (TM) – computable languages and functions –Turing Machine constructions – Storage in finite control – variations of TMs – Recursive and Recursive enumerable languages, Recursive Function, Partial and Total Recursive Function, Primitive Recursive Function.
Introduction to Computational Complexity: Time and Space complexity of TMs –Complexity classes – Introduction to NP-Hardness and NP-Completeness.
Hope this page was useful.
Regards,
TweakTag Team.