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/abSo 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