Regular vs Context Free Grammars

by

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.

More Related Contents:

  1. Finding the complement of a DFA?
  2. Regular expression [ 1 ( 0 1* 0)* 1 ]* DFA
  3. The recognizing power of “modern” regexes
  4. Is C++ context-free or context-sensitive?
  5. Left-Linear and Right-Linear Grammars
  6. Is it possible for a computer to “learn” a regular expression by user-provided examples?
  7. Tips for creating “Context Free Grammar”
  8. Need Regular Expression for Finite Automata: Even number of 1s and Even number of 0s
  9. drawing minmal DFA for the given regular expression
  10. Example of Non-Linear, UnAmbiguous and Non-Deterministic CFL?
  11. Grammatical inference of regular expressions for given finite list of representative strings?
  12. What is the language of this deterministic finite automata?
  13. How does “δ:Q×Σ→Q” read in the definition of a DFA (deterministic finite automaton)?
  14. Is a*b* regular?
  15. What is a Context Free Grammar?
  16. Why is {a^nb^n | n >= 0} not regular?
  17. Design DFA accepting binary strings divisible by a number ‘n’

Leave a Comment