Doubt

Question

L  =  { aⁿ b^m c^p d^q , n != m or p != q }

Is it inherently ambiguous or not????

Answer 1

L  =  { aⁿ b^m c^p d^q , n != m or p != q }  where n,m,p,q>=0

If there is no unambiguous grammer present for a given language then such a language is called inheritly ambiguous.

But for given language, unambiguous grammer exists

S→XY

X→X₁B|AX₁

X1→aX₁b|ϵ

B→bB|b

A→aA|a

Y→Y₁B|AY₁

Y₁→aY₁b|ϵ

B→bB|b

A→aA|a

So,given language is not inheritly ambiguous.

Comments

The grammar you have given is wrong bcoz it will not accepty the string

a^2 b^2 c^2 d.

---

@rahul jain25 u have taken wrong example..a power  cant be equal to b power..i.e.a^2≠ b^2

---

Question says OR not AND hence only one condition satisfying is enough, so my example is correct bcoz n(c) != n(d)

---

ya realize that..thanks

Answer 2

I think grammar will be inherently  ambiguous s-xy/zr

X-at1/t1b

t1-at1b/€

y-cyd/€

z-azb/€

r-cl1/l1d

l1-cl1d/€