Regular vs Context Free Grammars

Question

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 1

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.