Regular vs Context Free Grammars
I'm studying for my computing languages test, and there's one idea I'm having problems wrapping my head around.
I understood that regular grammars are simpler and cannot contain ambiguity, but can't do a lot of tasks that are required for programming languages. I also understood that context-free grammars allow ambiguity, but allow for some things necessary for programming languages (like palindromes).
What I'm having trouble with is understanding how I can derive all of the above by knowing that regular grammar nonterminals can map to a terminal or a nonterminal followed by a terminal or that a context-free nonterminal maps to any combination of terminals and nonterminals.
Can someone help me put all of this together?
Answer
Regular grammar is either right or left linear, whereas context free grammar is basically any combination of terminals and non-terminals. Hence you can see that regular grammar is a subset of context-free grammar.
So for a palindrome for instance, is of the form,
S->ABA
A->something
B->something
You can clearly see that palindromes cannot be expressed in regular grammar since it needs to be either right or left linear and as such cannot have a non-terminal on both side.
Since regular grammars are non-ambiguous, there is only one production rule for a given non-terminal, whereas there can be more than one in the case of a context-free grammar.