recategorized by
3,974 views
3 votes
3 votes

The grammar ‘GI’ $S \rightarrow OSO \mid ISI \mid 0 \mid 1 \mid \in$ and the grammar G2 is $ S \rightarrow as \mid asb \mid X, X \rightarrow Xa \mid a$.

Which is the correct statement?

  1. G1 is ambiguous, G2 is unambiguous
  2. G1 is unambiguous, G2 is ambiguous
  3. Both G1 and G2 are ambiguous
  4. Both G1 and G2 are unambiguous
recategorized by

2 Answers

Best answer
4 votes
4 votes
G2 IS AMBIGUOUS:

TAKE STRING aaa IN WHICH WE HAVE TWO LEFT MOST DERIVATION

S-->aS-->aX-->aXa-->aaa

AND

S-->aS-->aaS-->aaX-->aaa

SO AMBIGUOUS

G1 IS NOT AMBIGIOUS COZ WE CANT HAVE TWO DERIVATION TREE FOR A SINGLE SAME STRING

SO OPTION B IS CORRECT
selected by
1 votes
1 votes

G2 is Ambiguous grammar

G1 is Unambiguous grammar from which we can generate {O0O,O1O,I0I,I1I,OO0OO,OO1OO,II0II,II1II,OI0IO,OI1IO......}

Answer :B

Answer:

Related questions

6 votes
6 votes
2 answers
2
go_editor asked Jul 13, 2016
9,629 views
The minimum number of states of the non-deterministic finite automaton which accepts the language$\{ a b a b^n \mid n \geq 0 \} \cup \{ a b a^n \mid n \geq 0 \}$ is3456
1 votes
1 votes
1 answer
4
shivani2010 asked Jun 18, 2016
824 views
Which of the following regular expression identifies are true?(r+s)*=r*s*(r+s)*=r*+s*(r+s)*=(r*s*)*r*s*=r*+s*