Automata

Introduction of context free grammar

Context free grammar are Type 2 grammar in Chomsky hierarchy of grammar classification
How do we identify CFG ?

	A -> alpha,     A ε Variable, alpha ε (Variable U Terminal)*
Note: Variables are symbols in Caps

Example
	A -> aAbb/ab
So we can get output as "aabbb" if you replace the output of state A in its producitons.

Categories of CFG

  • Ambiguous vrs Unambiguous
  • Deterministic vrs Non-Deterministic
  • Left Linear vrs Right Linear
Note: CFG could be combination of above categories as well. eg.: ambiguous and right linear CFG

Machine used for CFG

Machines which are used to implement CFG are Push Down Automata aka PDA.