0
$\begingroup$

Is the language $L=\{a^nb^n\} \cup \{aa*\}$ DCFL OR CFL? The author says $L$ is CFL, but I am able to generate a Deterministic PDA for the corresponding language. I am naive in this subject and hence I am not sure whether its DCFL or CFL.

Can you provide an explanation that shows $L$ is either DCFL or CFL?

i dont know how to use math,i searched for the solution but didn't got any,my DPDA is shown in picture below.

enter image description here

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Please show your DPDA. $\endgroup$ – vonbrand Jan 8 '16 at 2:48
  • 1
    $\begingroup$ 1. What have you tried? What approaches have you considered? What research have you done? We expect you to do a significant amount of research before asking, and to show us in the question what you've done. 2. What specifically are you unsure about? If you have a DPDA for the language, it's a DCFL. Please show your DPDA. Have you tried proving your DPDA correct? If not, that's what you should do. 3. I encourage you to full sentences. 4. Please don't use images for math. You can use LaTeX for that. $\endgroup$ – D.W.♦ Jan 8 '16 at 4:19
  • $\begingroup$ i don't know how to use math or latex.problem is author says its CFL and i think i am doing mistake somewhere.also in other questions is specified it Its DCFL $\endgroup$ – Vivek Barsopia Jan 8 '16 at 5:08
2
$\begingroup$

Your PDA isn't deterministic, as it has moves for $q_0, \epsilon, a$ and $q_0, b, a$.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

Of course $\{ a^nb^n \mid n\ge 1\}$ is a DCFL. Adding $a^*$ to a DPDA for that language is straigthforward: as long as we did only read $a$'s that state we are in is final, after we read a $b$ the states are as in the original DPDA.

In this way we can show that the family DCFL is closed under union with regular languages. The construction simulates the original DPDA with a (deterministic) finite state automaton in parallel, using a product construction.

But there is a caveat. The original DPDA is deterministic, but it might end some of its computatuins in an infinite $\varepsilon$-loop. This will infinitely interrupt the simulation of the parallel finite automaton. Hence we need the requirement that the DPDA we start with has no such $\varepsilon$-loops. That is non-trivial, but as a normal-form it has been obtained in the construction for closure under complement for DCFL.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.