Peter Linz Exercise 8.1

Question

#10 Is the below language context free?

L = { w₁cw₂ : w₁,w₂ ∈ {a,b}^* , w₁≠ w₂}

As per my analysis it is not. Please verify.

Answer 1

Yes, It's not context free. 

Comments

@Ayush Upadhyaya

if it is like |w1| != |w2|

or if it is like |w1| = |w2|

then it will be dcfl right ??

---

@Ayush Upadhyaya

As given in peter linz:

This language is CFL. Construct an NPDA that counts to some value k (by putting k tokens on the stack) and remembers the kth symbol. It then examines the kth symbol in $w_{2}$. If this does not match the remembered symbol, the string is accepted.

If $w \ \epsilon\ L$ , there must be some k for which this happens. This npda chooses the k non-deteministically.

---

What if w1w2 instead of w1cw2

Answer 2

Not context free according to me.

Comments

The base case I found out was that we would exactly be not able to determine when to push symbols onto the stack and when to pop off.What was your's?

---

I thought as w1 is not equal to w2,it can be either less than or greater than w2.Lets assume w1>w2,if we push w1,skip c and try to pop w2,then there would be some symbols left in the stack and hence not context free as stack is not getting empty here.

Answer 3

Here push pop is clear but either w1 > w2 or w2 > w1 .  So stack may not be empty.

So not CFL.

Comments

if w1 > w2 or vice versa then w1 != w2 so we can easily tell this is not accepted hence CFL.