recategorized by
6,217 views
4 votes
4 votes

The Greibach normal form grammar for the language $L=\{a^n b^{n +1} \mid n \geq 0 \}$ is

  1. $S \rightarrow a \, SB, B \rightarrow bB \mid \lambda$
  2. $S \rightarrow a \, SB, B \rightarrow bB \mid b$
  3. $S \rightarrow a \, SB \mid b, B \rightarrow b$
  4. $S \rightarrow a \, Sb \mid b$
recategorized by

2 Answers

3 votes
3 votes

(A)S→aSB , B→bB ∣ λ

From this grammar we can't able to generate any string because there is no terminal string present for S.hence we can eliminate this option.

(B)S→aSB , B→bB ∣ b

From this grammar we can't able to generate any string because there is no terminal string present for S.hence we can eliminate this option.

(C)S→aSB ∣ b , B→b

From this we can generate all required string (b,abb,aabbb.....).

(D)S→aSb ∣ b

From this we can generate all required string (b,abb,aabbb.....) but question asking for GNF and this grammar is not GNF.

Hence,Option(C)S→aSB ∣ b , B→b is the correct choice.

edited by
2 votes
2 votes

ans is C it is in GNF and also produces the strings of type 

anbn+1n0

choice A  and B are in GNF but do not produce the above language as S is non terminating 

choice D is not in GNF as S->aSb is a violation of GNF

A CFG is said to be in Greibach normal form   (GNF)

if all productions have the form 

A->ax

where a ∈ T ,   x∈V*           i.e terminal and vertices respectively

or 

formal language theory, a context-free grammar is in Greibach normal form (GNF) if the right-hand sides of all production rules start with a terminal symbol, optionally followed by some variables. A non-strict form allows one exception to this format restriction for allowing the empty word (epsilon, ε) to be a member of the described language. The normal form was established by Sheila Greibach and it bears her name.

More precisely, a context-free grammar is in Greibach normal form, if all production rules are of the form:

A\to aA_{1}A_{2}\cdots A_{n} or S->

ab

Answer:

Related questions

2 votes
2 votes
1 answer
2
3 votes
3 votes
2 answers
3
2 votes
2 votes
1 answer
4
go_editor asked Jul 29, 2016
2,175 views
Which of the following commands would return process_id of sleep command?Sleep 1 and echo $Sleep 1 and echo $#Sleep 1 and echo $*Sleep 1 and echo $!