2
$\begingroup$

I need some help to prove that a Regular Language is closed under the union, using a DFA with two differents alphabets.

$\endgroup$
1
  • $\begingroup$ Have you seen the normal proof that the union of two regular languages on the same alphabet is closed? If so, take a moment and think why having two different alphabets doesn't really change anything. If not, you're probably ahead of yourself. $\endgroup$ Mar 9, 2016 at 6:31

2 Answers 2

3
$\begingroup$

Suppose you have alphabets $\Sigma\subseteq\Sigma'$. You can view any language $L\subseteq \Sigma^*$ as being a subset of $(\Sigma')^*$: it just happens to be language of strings that don't contain any symbols from $\Sigma'\setminus\Sigma$.

So, given languages $L_1\subseteq \Sigma_1^*$ and $L_2\subseteq\Sigma_2^*$, you can view both of these as languages over $\Sigma_1\cup\Sigma_2$, since $\Sigma_i\subseteq \Sigma_1\cup\Sigma_2$ for $i\in\{1,2\}$. Given automata for $L_1$ and $L_2$, you can also modify them to work over alphabet $\Sigma_1\cup\Sigma_2$.

Now, you have two languages over the same alphabet, so you should be on familiar ground.

$\endgroup$
2
  • $\begingroup$ I see now, my dificulty is the function of transition of the DFA, I need to change it, and can't see how. Any advice? $\endgroup$
    – user47613
    Mar 9, 2016 at 12:11
  • $\begingroup$ If $L\subset\Sigma^*$ then what do you know about a string that contains some character not in $\Sigma$? $\endgroup$ Mar 9, 2016 at 16:14
3
$\begingroup$

Using the accepted answer by @David Richerby -> I think what we have to do is modify the DFAs that recognize L1 and L2. Let L1 alphabet Σ1 and L2 alphabet Σ2,

let Σ = Σ1 ∪ Σ2

let's say we have DFA for L1 called M, For M DFA add a extra state called y and for all the letters in Σ but not in Σ1 add a transition from all the states of M to state y. then for all the letters in Σ add a transition from y state to y. Then we have a new DFA (let's call it M1) that recognize the same strings as M DFA but, over Σ alphabet rather than Σ1 alphabet.

we can do the same for L2 language and create a modified DFA with alphabet Σ.

Then we can use them to create a new DFA that can prove the Regular Language is closed under Union given two languages with different alphabets.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.