# Check if given language is CFL

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.

• What do you think about your approach? Have you tried proving it correct? Do you have a question about a specific thing? – Raphael Aug 2 '17 at 18:54
• cs.stackexchange.com/q/18524/755 – 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.
• This is an awful argument. Try it on the languages $\{a\}$ and $\{b\}$, for example (not to mention any DCFL language and itself). – Yuval Filmus Aug 2 '17 at 18:54