Automata Languages & Computations – Study Notes

  • Post author:
  • Post category:ALC / CSE / IT / Notez
  • Post comments:0 Comments
  • Reading time:2 mins read

Hello tweaktaggers, this write up is for the jotes in Automata Languages and Computation for any computer science majors, especially for Information Technology. Here we go with a list with the topics.

Unit I
Finite Automata and Regular Expressions: Deterministic and Non-Deterministic Finite Automata, Finite Automata with ?-moves, regular expressions – equivalence of NFA and DFA, two-way finite automata, Moore and Mealy machines, applications of finite automata.


Unit II
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; minimization of finite automata.


Unit III
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.


Unit IV
Turing machines: Turing machines(TM) – computable languages and functions – tuning machine constructions – storage in finite control – variations of TMs – recursive and recursive enumerable languages.


Unit V
Introduction to Computational Complexity: Time and Space complexity of TMs –
complexity classes – introduction to NP-Hardness and NP-Completeness.


Hope this article was useful, for you.


TweakTag Team.

Leave a Reply