Subjects
Books
Question: 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.
0

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: Dec 2015
mumbai university theory of computer science • 921 views
ADD COMMENT • link •
modified 3.3 years ago  • written 3.3 years ago by gravatar for Pooja Joshi Pooja Joshi • 740
0

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.
ADD COMMENT • link
written 3.3 years ago by gravatar for Pooja Joshi Pooja Joshi • 740
Please log in to add an answer.
Recommended

Similar posts • Search »

  • Nothing matches yet.