# Is the language $L=\{a^nb^n\} \cup \{aa*\}$ DCFL?

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.

• Please show your DPDA. – vonbrand Jan 8 '16 at 2:48
• 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. – D.W. Jan 8 '16 at 4:19
• 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 – Vivek Barsopia Jan 8 '16 at 5:08

Your PDA isn't deterministic, as it has moves for $q_0, \epsilon, a$ and $q_0, b, a$.
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.
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.