0
$\begingroup$

Note: FA = Finite Automaton

Given that N1 and N2 are the finite automatas that recognise A and B respectively, I know that N1 and N2 needs to be combined into a new automation N that starts in the initial state of N1. Then, empty transitions have to be added from the accepting states of N1 to the initial states of N2 and finally, the accepting states of N have to be set to be the accepting states in N2.

I just have no idea how to prove this formally. Any help would be greatly appreciated.

  • 0
    It's not worth an edit, but the singular is "automaton" and the plural is "automata".2012-10-17

1 Answers 1

1

You don’t need any empty transitions. I’m working with non-deterministic automata.

Let $N_1=\langle\Sigma,S_1,s_0,\delta_1,A_1\rangle$, where $\Sigma$ is the alphabet, $S_1$ is the state set, $s_0$ is the initial state, $\delta_1:S_1\times\Sigma\to\wp(S_1)$ is the transition function, and $A_1\subseteq S_1$ is the set of acceptor states. Similarly, let $N_2=\langle\Sigma,S_2,t_0,\delta_2,A_2\rangle$. Assume without loss of generality that $S_1\cap S_2=\varnothing$.

Now let $N=\langle\Sigma,S,s_0,\delta,A_2\rangle$, where $S=S_1\cup(S_2\setminus\{t_0\})$ and $\delta:S\times\Sigma\to S$ is defined as follows:

$\delta(s,\sigma)=\begin{cases} \delta_1(s,\sigma),&\text{if }s\in S_1\setminus A_1\\ \delta_2(s,\sigma),&\text{if }s\in S_2\\ \delta_1(s,\sigma)\cup\delta_2(s,\sigma),&\text{if }s\in A_1\;. \end{cases}$

Suppose that $x=\sigma_1\dots\sigma_m\in L(N_1)$. Then there are states $s_1\dots,s_m\in S_1$ such that $s_k\in\delta_1(s_{k-1},\sigma_k)\quad\text{for}\quad k=0,\dots,m\tag{1}$ and $s_n\in A_1$. Similarly, if $y=\tau_1\dots\tau_n\in L(N_2)$, there are states $t_1,\dots,t_n\in S_2$ such that $t_k\in\delta_2(t_{k-1},\tau_k)\quad\text{for}\quad k=0,\dots,n\tag{2}$ and $t_n\in A_2$.

For $k=0,\dots,m$ let $q_k=s_k$, and for $k=m+1,\dots,m+n$ let $q_k=t_{k-m}$. $(1)$ implies that $q_k\in\delta(q_{k-1},\sigma_k)\quad\text{for}\quad k=0,\dots,m\;,\tag{3}$ and $(2)$ implies that $q_k\in\delta(q_{k-1},\tau_{k-m})\quad\text{for}\quad k=m+2,\dots,m+n\;,\tag{4}$ with $q_{m+n}=t_n\in A_2$. Finally, $s_m\in A_1$, so the third part of the definition of $\delta$ shows that $q_{m+1}\in\delta_2(t_0,\tau_1)\subseteq\delta(q_m,\tau_1)\;.\tag{5}$ The word $xy$ is therefore accepted by $N$ with the computation combining $(3),(5)$, and $(4)$.

To finish the job you must show that if $w\in L(N)$, then $w\in L(N_1)\cdot L(N_2)$. Suppose that $w=\sigma_1\dots\sigma_n\in L(N)$. Then there are states $q_0=s_0,q_1,\dots,q_n\in S$ such that $q_n\in A_2$ and $q_k\in\delta(q_{k-1},\sigma_k)\quad\text{for}\quad k=0\dots,n\;.$ Note that $q_n\in A_2\subseteq S\setminus S_1$. Let $m=\min\{k\in\{1,\dots,m\}:q_m\in S\setminus S_1\}$. To finish the argument, show that $q_{m-1}\in A_1$ and $q_m\in\delta_2(t_0,\sigma_m)$, and conclude that $\sigma_1\dots\sigma_{m-1}\in L(N_1)$ and $\sigma_m\dots\sigma_n\in L(N_2)$.

  • 0
    Thanks for the clear explanation. I need more practice with formal proofs.2012-10-17