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

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.