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
  • $\begingroup$ What are E and null? $\endgroup$ – Raphael Feb 5 '13 at 10:15

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.)

  • 1
    $\begingroup$ Maybe the second one is an attempt on conversion to CNF? $\endgroup$ – Jakub Lédl Feb 4 '13 at 22:54
  • $\begingroup$ To be fully precise, the right hand side can't be $\epsilon$ (null above) either. But one of the standard transformations is to eliminate productions with $\epsilon$ on the right hand side, so in practice this is accepted. $\endgroup$ – vonbrand Feb 4 '13 at 23:15
  • 1
    $\begingroup$ @vonbrand - I'm not sure what you mean; a context-free grammar is allowed to have epsilon-transitions. $\endgroup$ – usul Feb 5 '13 at 1:36
  • $\begingroup$ @usul, if yu go by Chomsky's hierarchy of grammars, if it has $\epsilon$ as a RHS in a production, it is an unrestricted grammar (type 0). Nitpicking is one of my hobbies ;-) $\endgroup$ – vonbrand Feb 5 '13 at 1:50
  • $\begingroup$ @vonbrand - It is good to be picky about correctness, but I think there's a mistake somewhere. Otherwise no language containing the empty string would be context-free. Can you check your source? I am looking at Sipser's Intro to the Theory of Computation and there is no such restriction on CFGs ... even when put in Chomsky Normal Form, the start symbol is explicitly allowed to transition to $\varepsilon$. $\endgroup$ – usul Feb 5 '13 at 1:58

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


  • 1
    $\begingroup$ To be precise, what you describe as context-sensitive grammars are actually noncontracting (or monotonic) grammars. Context-sensitive grammars have the requirement that all rules are in the form $\alpha A \beta \rightarrow \alpha \gamma \beta$, where $A$ is a nonterminal and $\alpha, \beta, \gamma$ are strings of terminals and nonterminals ($\alpha$ and $\beta$ can be empty), therefore any context-sensitive grammar is also noncontracting. These two definitions are equivalent (i.e. they describe the same set of languages) and together form what is called the set of Type-1 grammars. $\endgroup$ – Jakub Lédl Feb 5 '13 at 14:05
  • 1
    $\begingroup$ Also, technically speaking, recursively enumerable and noncontracting grammars don't really make a distinction between terminal and nonterminal symbols, and the LHS in Type 0 grammars cannot be empty. $\endgroup$ – Jakub Lédl Feb 5 '13 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.