$L = \left \{ ab^{n}a^{n}|n>0 \right \} \bigcup \left \{ aab^ka^{2k} | k>0 \right \}$

What can be said about the given language L ?

According to me, I think it is CFL and not DCFL as I tried to somehow parse it through a NPDA but not sure though.


The words in the first part start with $ab$, those in the second part start with $aa$.

That should help.

| cite | improve this answer | |
  • $\begingroup$ Yes, thats what came in my mind first. But, I wasn't sure that am I going right . $\endgroup$ – Garrick Dec 26 '16 at 13:39
  • $\begingroup$ And how do you use this, concerning your CFL vs. DCFL question? $\endgroup$ – Hendrik Jan Dec 26 '16 at 15:10
  • $\begingroup$ I tried to design a PDA and this language has 2 sublanguages which will be parsed parallely, i.e, one more copy of the same PDA will be running parallely. Am I right ? $\endgroup$ – Garrick Dec 26 '16 at 17:45
  • 1
    $\begingroup$ Well, I would not phrase it as two copies in parallel, but I guess that is basically OK. Two parts of the PDA for the two parts of the language. Again: what does this mean for your CFL vs. DCFL question? $\endgroup$ – Hendrik Jan Dec 26 '16 at 17:55
  • $\begingroup$ Sorry, didn't get you. My friend gave me explaination that its a DCFL. And I was confused as i can make a PDA. Thats why, just wanted to confirm. Your comment is making me think I am missing something. Am I ? $\endgroup$ – Garrick Dec 26 '16 at 18:41

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.