1
$\begingroup$

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

In this exercise I am not given any alphabet and I'm required to build a PDA for $L_{12}$. But by definition $M=\left \{Q,\sum,\Gamma,\delta ,q_0,\dashv,F\right\}$ and I don't have any alphabet to work with. By intuition similar alphabets can affect the solution differently than dissimilar alphabets.

$\endgroup$
3
  • 1
    $\begingroup$ $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? $\endgroup$
    – user114966
    Jul 14, 2020 at 20:27
  • $\begingroup$ @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? $\endgroup$ Jul 14, 2020 at 20:39
  • 1
    $\begingroup$ The same language was considered earlier: For any two regular languages A, B, show that {xy|x ∈ A, y ∈ B, |x| = |y|} is context-free. There the alphabet was left unkown, or abstract. It just was named $\Sigma$ in the answer. In problems like this the actual alphabet does not really matter. In constructions we usually write things like "for every letter $\sigma\in \Sigma$ we ...". $\endgroup$ Sep 8, 2021 at 18:12

2 Answers 2

0
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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).

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

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.