Context Free language

Question

0^i1^j0^k|j=max(i,k) is CFL or not pls explain?

Answer 1

Think of the case when i=k,

In that case the Language will be 0ⁿ1ⁿ0ⁿ  Which is definitely a CSL.

So the language is not CFL.

Also, there can be other ways of proving the same such as considering the cases where i>k or i<k but this was the fastest I could think of.

Comments

OK think j=max(2,3) hence j=3 now j=k=3 hence without worrying for i we will push j into the stack and then pop it with k because it is no where wriitten that j should be checked with leading 0's.Now think j=max(3,2) now j=i=3 and no matter what was k because now we have j=i=3 therefore we will push 0 and pop with 1 and after reaching 0^k we will just read it. Hence we can make NPDA for these two cases.

 

Correct me if i am wrong?

---

Hash is at the bottom of the stack

lets take case 1:
i=2

You push 2 zeroes.                                                                                                   # 0 0

Now you see 3 ones coming, Let's assume, you push them in                        # 0 0 1 1 1

Now you see 3 trailing zeroes coming, you pop 1 one for each 0                   # 0 0

At this point of time, do you think you compared i and k anywhere

Then how would the PDA know that i was actually less than k?

---

Thank u bro i got it