recategorized by
4,679 views
5 votes
5 votes

Given the following grammars:

$G_1$ $S \rightarrow AB \mid aaB$
  $A \rightarrow aA \mid \epsilon$
  $B \rightarrow bB \mid \epsilon$
$G_2$: $S \rightarrow A \mid B$
  $A \rightarrow a A b \mid ab$
  $B \rightarrow abB \mid \epsilon$

Which of the following is correct?

  1. $G_1$ is ambiguous and $G_2$ is unambiguous grammars
  2. $G_1$ is unambiguous and $G_2$ is ambiguous grammars
  3. both $G_1$ and $G_2$ are ambiguous grammars
  4. both $G_1$ and $G_2$ are unambiguous grammars
recategorized by

4 Answers

Best answer
4 votes
4 votes

Here both G1 and G2 are ambiguous 

G1 : We can generate 2 parse tree for string aab

                S                                                                   S

             /     \                                                             /  |  \

          A         B                                                          a   a    B

        /  \        /  \                                                                 /  \

     a      A    b     B                                                             b     B

           /  \          |                                                                     |

         a     A        ∊                                                                     ∊

                     |

                     ∊

G2: We can generate more than one parse tree for ab.

                   S                                                                  S

                   |                                                                    |

                   A                                                                   B

                 /  \                                                               /  |  \

              a       b                                                         a     b    ∊ 

Hence,Option(C)Both G1 and G2 are ambiguous grammars. 

selected by
6 votes
6 votes

Both are ambiguous since 1st for aa and second for ab has two derivation tree.

C is answer

2 votes
2 votes

OPTION 3. BOTH GRAMMER ARE AMBIGUOUS

DEFN:  FOR ANY STRING IF THERE IS MORE THEN ONE LEFT DERIVATION TREE  OR RIGHT DERIVATION TREE EXIST THEN IT IS AMBIGUOUS.

NOW CHECK 

FOR G1: TAKE STRING  {aa}

DERV   1.   S->AB->aAB->aaAB->aaB->aa   (ALL ARE LEFT MOST DERIVATION)

DERV   2.    S->aaB->aa

SO AMBIGUOUS

FOR G2:  TAKE STRING     {ab}

DERV 1.   S->A->ab

DERV 2.   S->B->abB->ab

SO AMBIGUOUS

0 votes
0 votes

If We have more than one LMD or more than one RMD or more than one Parse Tree, then grammar will be ambiguous:

G1 : for string aa

         s->aaB == aa (B->epsilon)

         s->AB == aAB (A->aA) == aaAB (A->aA) == aaB (A->epsilon) == aa (B->epsilon)

G2 : for string ab

        s->A == ab (A->ab)

        s->B == abB (B->abB) == ab (B->epsilon)

Hence G1 and G2 both are ambiguous.

Option C

Answer:

Related questions

3 votes
3 votes
2 answers
4
go_editor asked Jul 31, 2016
6,456 views
The regular expression corresponding to the language L where $L=\{ x \in \{0,1\}^* \mid x \text{ ends with 1 and does not contain substring 00} $ is(1+01)* (10+01)(1+01)*...