Following language: L = {a^n b^n c^n d^n , n ≥ 1} ,How it is CSL and not CFL?

Question

My understanding :

We can create PDA as follows

for every 'a' push operation and on 'b' pop operation and again on 'c' push operation and  on seeing 'd' pop operation.

please correct me , if i am wrong.

I am sorry, if it is not important.

Thanks lot :)

Comments

Is this a CFL?

Answer 1

In PDA if you pop a for every b, then after number of a's and b's are equal  Stack will be empty.

Then you have nothing to compare the number of incoming c's with previously read number of a's or b's.

So, it is not sure that number of a's or b's will be equal to that of c's.

Comments

what will be the steps then for CSL...??

Answer 2

Pda supports only two comparisons... For ur ques pda requires more than one stack.. Hence above one is CSL

Comments

PDA supports only 1 comparison.

---

More than one stack becomes LBA so it is CSL

Answer 3

If we see..

L1: a^mb^nc^n|n,m>=1 CFL
L2:a^mb^mc^n|n,m>=1 CFL

L: L1 intersection L2 =  a^nb^nc^n |n>=1 =CSL
That is not clouser under intersection

Bcoz PDA NOT POSSIBLE - WE NEED 2 COMPRESSION AT A TIME.
i'e 2 stack required.....but in PDA ONLY NEED 1 STACK

There for ANS is CSL ;