DCFL or Not

Question

$\left \{ a^{m+n}b^{m+n}c^{n}|m,n\geq 1 \right \}$

$\left \{ a^{m+n}b^{m+n}c^{k} |m,n,k\geq 1\right \}$

$\left \{ a^{m+n}b^{m+k}c^{n+k} |m,n,k\geq 1\right \}$

Which one DCFL, CFL or CSL?

Comments

CSL, DCFL and CSL.

---

@Kapil after a long day :)

Can 3rd one be done in 2 stacks?

---

CSL can performed in 2 stacks, rt?

---

FA with 2 stacks behaves like CSL.

---

This can be done with 2 stacks.

---

@Kapil , I think 3rd one is DCFL...It can be written as aⁿa^mb^mb^kc^kcⁿ... I think one stack is enough for this language..please correct me if I m wrong..

---

1. CSL 2.DCFL 3. CFL.

---

@ankit, that looks correct.

---

can you explain how 2nd is DCFL? I know if 2nd one is DCFL then 3rd also DCFL.... Coming to 2nd, let assume m=5 and n=6, I know the whole is 11 therefore consecutive 11 a's and 11 b's can be accepted by DPDA..But According to me in 2nd one.. a^m+n b^m+n then 5 a's,6 a's, and 6 b's,5 b's is also accepting. Right??

---

@ankit how the third one is dcfl

Suppose n=2,m=3,k=4

Then total a will be 5 if we will push 5 a's then 7 b's will come then how to know that how many a's to popped off, after 5 pop stack will be empty .

---

@Prince Sindhiya , your  reasoning is absolutely correct that how machine will know that it has to pop m a's because machine don't have the capability of counting..So, I was wrong.

I don't know whether it is CFL or not.

a^m+nb^m+kc^n+k can be rewritten as a^n+mb^m+kc^n+k

now if we do union for m=1 , 2, .....

now if m=1 ,then aⁿ⁺¹m^1+kc^n+k

This can be accepted by DCFL.. Push the a's until we see b. Then pop once. There are now n symbols on stack. Push b's, until we see a c. There are now n+k symbols on stack. Pop all c's, accept if stack is empty.

if we do it for m=2,3,... then it will become infinite union..and  DCFLs are not  closed under infinite union..it may be DCFL or may not be...if we consider a PDA which can do push and pop non-deterministically on the stack but PDA has finite number of states but here I don't know whether infinite union takes infinite number of states or not..so it may or may not be CFL.. now I also don't know that LBA can accept this language with finite number of states or not... 

 

---

guys , We all were wrong. 3^rd one is CFL but not DCFL. It is confirmed by Prof. Shai Simonson. Reason is given in the below image...

---

@ankit I think u are right .

From where you read it that dcfl is not closed under infinite union?

---

@Prince , I have read it on internet..I don't have any authentic reference for it.

---

@ankit, can you clarify 2nd one ?

---

Yes because when b comes after few pop operation(as human we can see that there is only m no. of b's to pop) but machine don't know either to pop 'b' again or start pushing it but this can be guessed (for every b )on each step using Non-deterministicPDA .

---

here 2nd one?

---

@Shaik , push a's until we see 'b' ..so there are m+n symbols onto the stack. now pop stack by b's until we see 'c'..now on c , do nothing onto the stack and go to final state..it will be accepted by DPDA..

Answer 1

$\boldsymbol{\textbf{1.CSL 2.DCFL 3.CSL}}$

Comments

no see the comment section

Answer 2

first one is CSL

second one is CFL

third one is also CFL as when we are removing “a” from stack then only “m” a’s can be popped so that we are left with “k” a’s in stack. Then we push n b’s in the stack making total n+k b’s which can be further popped for c’s Hence 1 stack is sufficient.