Subjects
Books
0
Consider the following grammar G = (V, T, P, S), V = {S, X}, T {0, 1} productions P are S is start symbol. Show that above grammar is ambiguous.
written 3.5 years ago by gravatar for Pooja Joshi Pooja Joshi • 760 •   modified 3.5 years ago

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: Dec 2015
mumbai university theory of computer science • 967  views
0  upvotes
ADD COMMENT  
0
written 3.5 years ago by gravatar for Pooja Joshi Pooja Joshi • 760

Let,

S->0|0X1|01S1

X->0XX1|1S

enter image description here

As we get two different parse trees with one parse trees contains 0101 as input and other also contains 0101 but as a substring.

So, the given grammar is said to be ambiguous.
0  upvotes
ADD COMMENT  
Please log in to add an answer.

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.

Search

Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More