The Gateway to Computer Science Excellence
+3 votes
783 views

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
in Theory of Computation by Veteran (106k points)
recategorized by | 783 views

2 Answers

+4 votes
Best answer
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
by Boss (11.1k points)
selected by
+1 vote

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

by Loyal (8.7k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,834 questions
57,852 answers
199,514 comments
108,376 users