# Creating a Deterministic Push-Down Automaton for the Union of two languages

Suppose, we have $$L_1:=\{w\in\{a,b\}^*\mid \#_a(w) \equiv 0 \mod 4\}$$ and $$L_2:=\{w\in\{a,b\}^*\mid abaab \text{ is a substring of } w\}$$. Now we want to create a Deterministic Push-Down Automaton for $$L_1\cap L_2$$

I've created PDA's for both languages:

$$M'=(Q,\Sigma,\Gamma,\Delta,s,F)$$ with $$\Sigma=\{a,b\}$$, $$\Gamma=\{\}$$, $$Q=\{1,2,3,4\}$$, $$F=\{0\}$$, $$s=\{0\}$$ and \begin{align} \Delta=\{&(0,a,\lambda,1,\lambda),(0,b,\lambda,0,\lambda)(1,a,\lambda,2,\lambda),(1,b,\lambda,1,\lambda),(2,a,\lambda,3,\lambda),(2,b,\lambda,2,\lambda)\\ &(3,a,\lambda,0,\lambda),(3,b,\lambda,3,\lambda)\} \end{align} where $$\Delta\subseteq Q_{old}\times (\Sigma \cup \{\lambda\})\times(\Gamma\cup \lambda)\times Q_{new}\times\Gamma^*$$

and

$$M''=(Q,\Sigma,\Gamma,\Delta,s,F)$$ with definitions above and $$\Sigma=\{a,b\}$$, $$\Gamma=\{\}$$, $$Q=\{1,2,3,4,5,6\}$$, $$F=\{6\}$$, $$s=\{1\}$$ and \begin{align} \Delta=\{&(1,a,\lambda,2,\lambda),(1,b,\lambda,1,\lambda),(2,a,\lambda,2,\lambda),(2,b,3,\lambda),(3,a,\lambda,4,\lambda),(3,b,\lambda,1,\lambda),\\&(4,a,\lambda,5,\lambda),(4,b,\lambda,3,\lambda),(5,a,\lambda,2,\lambda),(5,b,\lambda,6,\lambda),(6,a,\lambda,6,\lambda),(6,b,\lambda,6,\lambda)\} \end{align}

$$M'$$ accepts $$L_1$$ and $$M''$$ accepts $$L_2$$, but how to construct $$M^{\star}=M'\cap M''$$ which accepts $$L_1\cap L_2$$?

I know, that we could possibly do this with Deterministic Finite Automata, but I want to know how it would work with PDA's.

There is no general algorithm for computing a DPDA $$M^*$$ as the intersection of two DPDA $$M,M'$$; that problem is undecidable. See Undecidable problem intersection of two DCFL languages is DCFL? for a proof.

So, you will have to look for some pattern in this particular problem that makes it easier than the general case. Hint: what level in the Chomsky hierarchy is $$L_1$$ at? what about $$L_2$$?

• They're both type 3 and we possibly don't need the stack of the PDA to compute them. Unfortunately I should use PDA's to do it... We heard something of the Union of 2 PDA's that only works with a PDA that needs the Stack and one PDA for a language of type 3 which doesn't need the stack so you can mix them up. One does things on the stack and the other one just works like a DFA... But I'm not sure how to really apply this all in this particular case. Commented Dec 7, 2019 at 22:09
• @Doesbaddel, great. So you know they are type 3. Could that be helpful? This is your exercise, so you'll need to take it from here. I suggest you spend some more time on it.
– D.W.
Commented Dec 7, 2019 at 22:09
• Yeah, I will try to do so. Can I use the algorithm for DFA's for intersection? Because both are of type 3 and then just change it to a PDA in the end? Commented Dec 7, 2019 at 22:13
• I've created DEA's for both languages. After that I created the DEA for the intersection and then minimized it. Out of that I created a push down automata that doesn't use the stack. Commented Dec 10, 2019 at 9:29
• @Doesbaddel, congratulations on solving the problem! Nice job.
– D.W.
Commented Dec 10, 2019 at 9:36