Assume language $L$ as follow:- $$ L = \{ a^n b^x c^m d^y | (n=m) \lor (x=y)\} $$ Is it possible to design DPDA/NPDA for this? I know if the condition would have been "and" then it is not possible. But is it possible with "or"?

My approach:- 1. Push all $a$'s to the stack.

  1. At $b$ define non deterministic behavior as follow:-

    2.1. Assume we are checking for $n=m$.So skip all the $b$'s.

    2.1.2.Whenever $c$ is encountered, pop $a$ for $c$.

    2.1.3. When $d$ is encountered check if stack is empty, if yes, then accept else reject.

    2.2. Assume we are checking $x=y$. So push all the $b$'s to the stack. Now when $c$'s are encountered skip them.

    2.2.1. When $d$'s are encountered, count them with $b$'s which are on top of stack.

    2.2.2. When input is finished and stack is empty or contains only $A$, then accept else reject.

  • 1
    $\begingroup$ What do you think about your approach? Have you tried proving it correct? Do you have a question about a specific thing? $\endgroup$ – Raphael Aug 2 '17 at 18:54
  • $\begingroup$ cs.stackexchange.com/q/18524/755 $\endgroup$ – D.W. Aug 2 '17 at 19:11

Note that $$ L = \{ a^n b^x c^n d^y : n,x,y \geq 0 \} \cup \{ a^n b^x c^m d^x : n,m,x \geq 0 \}. $$ Try showing that each of these is context-free individually.

  • $\begingroup$ Thanks.I was making it unnecessarily complex.It must be parsed by NPDA. DPDA will not be able to handle this.Am i correct? $\endgroup$ – rahul sharma Aug 2 '17 at 18:47
  • $\begingroup$ This seems right, but requires proof. $\endgroup$ – Yuval Filmus Aug 2 '17 at 18:48
  • $\begingroup$ I can use the properties.From your answer i can conclude that the two languages are DCFL, and DCFL are not closed under union.Hence the result(L) is not DCFL. Next in the hierarchy is CFL. And as CFL are closed under union ,hence L is CFL but not DCFL.Will this suffice? $\endgroup$ – rahul sharma Aug 2 '17 at 18:53
  • $\begingroup$ This is an awful argument. Try it on the languages $\{a\}$ and $\{b\}$, for example (not to mention any DCFL language and itself). $\endgroup$ – Yuval Filmus Aug 2 '17 at 18:54
  • $\begingroup$ I did't understand your point. Is my reasoning in the above question wrong?By DCFL are not closed under union i mean ,it may or may not be closed. $\endgroup$ – rahul sharma Aug 2 '17 at 18:59

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.