Theory of Automata 

Table of Contents

What does automata mean, Introduction to languages

Kleene Star Closure, Recursive definition of languages

Regular Expression, Recursive definition of Regular Expression

Equivalent Regular Expressions

Finite Automaton

Equivalent FAs

FA corresponding to finite languages

Examples of TGs: accepting all strings

Generalized Transition Graphs

Nondeterminism, Kleene’s Theorem

Proof(Kleene’s Theorem Part II)

Kleene’s Theorem Part III

Concatenation of FAs

Closure of an FA

Nondeterministic Finite Automaton, Converting an FA to an equivalent NFA

NFA with Null String

NFA and Kleene’s Theorem

NFA corresponding to Concatenation of FAs

Distinguishable strings and Indistinguishable strings

Finite Automaton with output, Moore machine

Mealy machine

Equivalent machines

Mealy machines in terms of sequential circuit

Regular languages, Complement of a language

Nonregular languages

Pumping Lemma

Pumping Lemma version II

Pseudo theorem

Decidability

finiteness of a language

Context Free Grammar (CFG), CFG terminologies

Trees

Polish Notation (ooo)

Total language tree, Regular Grammar

Null Production

Chomsky Normal Form (CNF)

A new format for FAs

Nondeterministic PDA

PDA corresponding to CFG

Conversion form of PDA

Conversion Form, Joints of the machine

Row language, Nonterminals

NonContextFree language, Pumping lemma for CFLs

Decidablity, Parsing Techniques

Turing machine

