Answer to Question #177409 in Algorithms for Shahrin trisha

Question

Prove the theorem

The elass of regular languages is closed under union operation. In othe words, if Al

and A2 are regular languages, so is (Ai UA2)"for the following languageL-twiw acepts even mumber of 'a' or even number of "b'.

Answer 1

Prove that for regular languages $L_1$ and $L_2$ that $L_1\lor L_2$ is regular.

Let $M_1=(S_1,\sum, \delta_1,s_1,F_1)$ and $M_2=(S_2,\sum, \delta_2,s_2,F_2)$ be DFA for $L_1$ and $L_2$

DFA Construction (the Product Construction):

We claim the DFA $M=(S_1\times S_2,\sum, \delta,(s_1,s_2),F)$ where

$\delta((s_1,s_2),a)=(\delta_1(s_1,a),\delta_2(s_2,a))$ for all $s_1\isin S_1,s_2\isin S_2$ and $a\isin \sum$ ,

$F=(F_1\times S_2)\lor (S_1\times F_2)$

accepts $L_1\lor L_2$

i.e. $L(M)=L(M_1)\lor L(M_2)$ .

Proof of correctness: For every string $w$ , we have:

$\hat{\delta}((s_1,s_2),w)=(\hat{\delta}_1(s_1,w),\hat{\delta}_2(s_2,w))$

$\hat{\delta}((s_1,s_2),w)\isin F$ iff $\hat{\delta}_1(s_1,w)\isin F$ or $\hat{\delta}_2(s_2,w)\isin F$ .

$L_1\lor L_2$ is regular since there is a DFA accepting this language.