#Gate CS Applied Course Mock Test

Question

Is this Language a CFL?

If yes, Can you please explain the implementation.

Comments

@ankit3009 correct. Just one correction in your comment

Here the language of both is compared

Here we are just having one language which is L, and we are not even comparing two string neither two language , just cheking each of the string present in L is having a specific property(w1 != w2) or not.

---

Checking via comparing only, right? 😅

In your earlier comment, you were comparing the first element of w1 and w2, that’s what we can’t do here as the first element of w1 will be at the lowest position and the first element of w2 will be encountered after the last element of w1. So, we can’t check here. So, it’s not a CFL.

---

Checking via comparing only, right?

Yes..everything is correct, I was just saying that language != string 

Answer 1

Yes it is CFL,in fact a much stronger statement would be a DCFL. why so ? You keep on pushing whatever is the input into the stack,the moment you see C , it gives u a hint to start popping off the symbols. And u start popping off the symbols, just see at the end if the stack becomes empty,here you should get non empty for it to get accepted 

Comments

That would be the case when we consider the lenghts of W1 and W2 but here the condition is W1 != W2.

Means the 2 Strings W1 and W2 should not be equal.

Correct me if i am wrong.

---

Yes u r right,my bad !!

Answer 2

As given in Peter Linz Book:

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 w2w2. If this does not match the remembered symbol, the string is accepted.

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

So Applied Ans is correct. So many places the ans is given as Non-CFL but its CFL. 

Link: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/viewer.html?pdfurl=https%3A%2F%2Ffall14cs.files.wordpress.com%2F2017%2F04%2Fan-introduction-to-formal-languages-and-automata-5th-edition-2011.pdf&clen=8631548&chunk=true