Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 1 down vote favorite

What is the correct way to write a CFG?

A -> B C' E
C' -> C
C' -> null

or

A -> B C'
C' -> C E
C' -> E
share|improve this question
What are E and null? – Raphael♦ Feb 5 at 10:15

migrated from cstheory.stackexchange.com Feb 4 at 22:18

2 Answers

up vote 5 down vote accepted

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

share|improve this answer
1  
Maybe the second one is an attempt on conversion to CNF? – Jakub Lédl Feb 4 at 22:54
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. – vonbrand Feb 4 at 23:15
1  
@vonbrand - I'm not sure what you mean; a context-free grammar is allowed to have epsilon-transitions. – usul Feb 5 at 1:36
@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 ;-) – vonbrand Feb 5 at 1:50
@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$. – usul Feb 5 at 1:58
show 5 more comments
up vote 2 down vote

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

:)

share|improve this answer
1  
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. – Jakub Lédl Feb 5 at 14:05
1  
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. – Jakub Lédl Feb 5 at 14:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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