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 understand 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 understand 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 grammer 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.

and since regular grammar are non-ambiguous, there is only one production rule for a given non-terminal, whereas there can be more than one in case of a context-free grammar.