What is the difference between context free grammar and an Other grammar? [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

What grammars are not context free? Please give me examples that are not context free.

Is this grammar context free?

A->aSb|aaS|aaaS|B
S->aSb|Bb|lambda
B->Bb|lambda

Answer 1

The grammar is context-free, because there's no context around the left-hand side. See below.

Assuming:

• The Greek letters like α, β, and γ are arbitrary productions
• Uppercase letters like X and Y are nonterminal symbols
• Lowercase letters like z are terminal symbols
• ε is the special empty production

We have the following definitions:

1. Regular grammars are those whose rules can be written in the forms:

   X: z Y
   X: z
   X: ε
   

   For example:

   Digits: '0' Digits
   Digits: '1' Digits
   Digits: '2' Digits
   ...
   Digits: '9' Digits
   Digits: ε
   

2. Context-free grammars are those whose rules can be written in the form:

   X: α
   

   In other words, only single nonterminals can be transformed at a time, independently of what might surround them.

   For example:

   Expression: AdditiveExpression
   AdditiveExpression: AdditiveExpression '+' MultiplicativeExpression
   AdditiveExpression: AdditiveExpression '-' MultiplicativeExpression
   AdditiveExpression: MultiplicativeExpression
   MultiplicativeExpression: MultiplicativeExpression '*' PrimaryExpression
   MultiplicativeExpression: MultiplicativeExpression '/' PrimaryExpression
   MultiplicativeExpression: PrimaryExpression
   PrimaryExpression: Number
   PrimaryExpression: '(' Expression ')'
   

3. Context-sensitive grammars are those whose rules can be written in the form:

   αXγ: αβγ
   

   In other words, the context around X can help you decide that X should be transformed into β, but the context itself does not become transformed.

   For example:

   Expression: 'x' Foo 'y'
   'x' Foo 'y': 'x' Bar 'y'
   Bar: 'z'
   

   A more realistic example that shows why this is useful can be found on Math.StackExchange.

4. Unrestricted grammars are those whose rules can be written in the form:

   αXγ: β
   

   In other words, any sequence of symbols containing a nonterminal can be manipulated into any other sequence of symbols. Basically, this represents arbitrary manipulation of memory, or Turing-completeness.

   For example:

   Expression: 'x' Foo 'y'
   'x' Foo 'y': 'z'
   

   You never see these in practice.