What is the correct way to write a CFG?
A -> B C' E C' -> C C' -> null
A -> B C' C' -> C E C' -> E
migrated from cstheory.stackexchange.com Feb 4 '13 at 22:18
This question came from our site for theoretical computer scientists and researchers in related fields.
Both of those are valid context-free grammars. (For the same language.) The requirement for a context-free grammar is just that the left side of the production must have exactly one non-terminal, which both of them satisfy. (Usually, to make this more clear, we'd have a convention like non-terminals are uppercase and variables are lower-case, and we'd specify the start symbol. But it looks clear that you have $A$ and $C'$ as nonterminals and the rest terminals, with $A$ being the start symbol.)
Conditions for Famous Grammars: (YOU MUST NEVER FORGET THE FOLLOWING)
1) Regular Grammars : Grammar That is either Right linear or Left Linear Grammar
This is also called Type 3 Grammar
2) Context Free Grammar : LHS must be exactly 1 Non-terminal , RHS can be any String of terminals and Non--Terminals.
This is also called Type 2 Grammar
3) Context Sensitive Grammar : LHS can be any String , RHS can be any String of terminals and Non--Terminals such that for each production , length of LHS string must be less than or equal to length of RHS string
This is also called Type 1 Grammar
4) Recursively Enumerable Grammar : LHS can be any String , RHS can be any String of terminals and Non--Terminals
This is also called Type 0 Grammar