Hi,
I have following language. I have to determine, if its context free or not.
L = {a^n b^j a^k b^l : n+j ≤ k+l}.

When n+j== k+l then it seems context free because we push 'n' number of 'a's and 'j' number of 'b's. We can cancel out with equal number of 'a's and 'b's if n+j == k+l. But if (n+j) < (k+l) then the stack would be empty but the other after the mid-point still exists. So the strings are not balance. So what we can say about this language?

Zulfi.

 

Consider a simpler language that has similar characteristics.

L = {a^n b^m | n ≤ m}

Is this context free?

Remember that you can establish that a language is context free either by designing a PDA that accepts it, or constructing a context-free grammar that generates it.

 

Hi,
Same problem We would first push 'a's 'n' time into npda and pop 'a's 'm' times when we hit the first 'b'. But 'm' is greater than 'n'. So we would have fewer 'n's so the stack would become empty but still we have 'b's. I don't know what to do at this point ?

Zulfi.

 

Hi,
Same problem We would first push 'a's 'n' time into npda and pop 'a's 'm' times when we hit the first 'b'. But 'm' is greater than 'n'. So we would have fewer 'n's so the stack would become empty but still we have 'b's. I don't know what to do at this point ?

Zulfi.

Why (or even how) would we pop 'a's 'm' times when we hit the FIRST 'b'?

If the stack becomes empty and you still have b's remaining, what does that tell you about whether the string is in the language?

How about the following:

L = {a^n b^n b^m | n,m ≥ 0}

 

Hi,
<Why (or even how) would we pop 'a's 'm' times when we hit the FIRST 'b'? >
We would pop one 'a' for each 'b' we come across. Ultimately we would reach the end of stack because number of b's is greater than or equal to 'a'. So we reach the end of stack but still we have b's.

<If the stack becomes empty and you still have b's remaining, what does that tell you about whether the string is in the language? >
At this point we can say that the string is accepted by the npda.

<
How about the following:

L = {a^n b^n b^m | n,m ≥ 0} >

In this case again the string is accepted by npda. Stack would become empty but still we would be left with b's.
Please provide the answers.

Zulfi

 

You are largely on the right track. First, hopefully you recognize that

L = {a^n b^m | n ≤ m}

and

L = {a^n b^n b^m | n,m ≥ 0}

are the exact same language.

Next, consider that

L = {a^n b^j a^k b^l : n+j ≤ k+l}.

is almost the same. Instead of having a's followed by b's only, you have a first portion with a's followed by b's followed by a second portion with a's followed by b's. But the logic about how to deal with it is virtually identical.

The other thing that you need to consider is that if you try to pop something from an empty stack, the machine dies. So if you need the machine NOT to die in that situation, what is the standard trick for accomplishing that?