# Build PDA for a language with unknown input alphabet

$$L_1 ,L_2$$ are regular language. We form a new language $$L_{12}$$ as follows: $$L_{12}=\left \{ w_1\cdot w_2|w_1\in L_1\wedge w_2\in L_2\wedge|w_1|=|w_2| \right \}$$

In this exersice I am not given any alphabet and I'm required to build PDA for $$L_{12}$$, but by definition $$M=\left \{Q,\sum,\Gamma ,\delta ,q_0,-|,F\right\}$$ and I don't have any alphabet to work with.By intuition if the alphabet is similiar can effect the solution than if it wasn't similiar.

• $L_1$ and $L_2$ have their alphabets $\Sigma_1$ and $\Sigma_2$. So it suffices to select $\Sigma = \Sigma_1 \cup \Sigma_2$ (since every word from $L_{12}$ is in this alphabet). Is this what you are asking? – Dmitry Jul 14 '20 at 20:27
• @Dmitry If I don't have any info on the alphabet, then how can I classify a certain situation in the PDA. Perhaps the model should be somewhat more general, because I need to make distinctions in the model that show if input belongs to the language or not but how can I do it without specific alphabet? – user6394019 Jul 14 '20 at 20:39

You might reason like this: If $$L_1, L_2$$ are regular, then $$L_2^R$$ is regular ($$L^R$$: reverse words). You can build regular grammars $$G_1 = (N_1, \Sigma_1, P_1, S_1)$$ and $$G_2 = (N_2, \Sigma_2, P_2, S_2)$$ that generate $$L_1$$ and $$L_2^R$$. The crucial point is that the regular grammars have the lonely non-terminal always at the end (or beginning!) of the sentential form. Build a CFG with nonterminals $$Q = N_1 \times N_2$$, and productions that build up $$L_1$$ to the left (using the first part of the nonterminal) and $$L_2^R$$ to the right (using the second part of the nonterminal, building from the end). From the resulting grammar you can build a PDA.

The basic idea is similar to the construction for $$\{ w w^R \colon w \in \Sigma^*\}$$ with $$S \to x S x$$ for all $$x \in \Sigma$$ and $$S \to \varepsilon$$ (or $$S \to xx$$ for purists).

Let $$\Sigma_1$$ be the alphabet for $$L_1$$ and $$\Sigma_2$$ be the alphabet for $$L_2$$. By definition, $$\Sigma_1,\Sigma_2$$ are both finite.

Then, assume $$\Sigma_1=\{\sigma_1,\sigma_2,...,\sigma_n\},\Sigma_2=\{\mu_1,\mu_2,...,\mu_k\}.$$

Now, define $$\Sigma=\Sigma_1\bigcup\Sigma_2$$ and let it be the alphabet for $$L_{12}$$.

Notice: In general, when talking about languages - we must specify what language we are working with (by definition of what a language is) - but usually we assume the binary alphabet ($$\Sigma_{bin}=\{0,1\}$$) or any other alphabet with 2 or more letters (more than two letters is just for ease of use), since you can encode every letter as a series of 0's and 1's. In rare cases, we might assume the unary alphabet ($$\Sigma_{unary}=\{1\}$$) but that is more useful (and you will see it probably) in Complexity Analysis (and not for PDA's and DFA's).

• Well, we may have empty alphabets as well... – J.-E. Pin Aug 19 '20 at 9:31
• Never saw an empty alphabet and I cannot think how it could have been useful to anyone :O – nir shahar Aug 19 '20 at 9:33
• You never use the fact that $\emptyset^* = \{1\}$? – J.-E. Pin Aug 19 '20 at 9:37