Automata Languages & Computations – ALC

  • Post author:
  • Post category:ALC / CSE
  • Post comments:0 Comments
  • Reading time:3 mins read

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.


TweakTag Team.

Leave a Reply