União de duas linguagens regulares

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Na teoria das linguagens formais, e em particular na teoria dos autômatos finitos não determinísticos, é conhecido que a união de duas linguagens regulares é uma linguagem regular. Este artigo fornece uma prova desta afirmação.

Teorema[editar | editar código-fonte]

Para quaisquer linguagens regulares L_{1} e L_{2}, a linguagem L_{1}\cup L_{2} é regular.

Prova

Uma vez que L_{1} e L_{2} são regulares, existem AFNs N_{1},\  N_{2} que reconhecem L_{1} e L_{2}.

Seja

 N_{1} = (Q_{1},\ \Sigma ,\ T_{1},\ q_{1},\ A_{1})
 N_{2} = (Q_{2},\ \Sigma ,\ T_{2},\ q_{2},\ A_{2})

Vamos construir

N = (Q,\ \Sigma ,\ T,\ q_{0},\ A_{1}\cup A_{2})

onde

Q = Q_{1}\cup Q_{2}\cup\{q_{0}\}
T(q,x) = \left\{\begin{array}{lll}
											T_{1}(q,x) & \mbox{se} & q\in Q_{1} \\
											T_{2}(q,x) & \mbox{se} & q\in Q_{2} \\
											\{q_{1}, q_{2}\} & \mbox{se} & q = q_{0}\ e\ x =\epsilon\\
											\emptyset & \mbox{se} & q = q_{0}\ e\ x\neq\epsilon
											\end{array}\right.

Em seguida, vamos usar p\stackrel{x,T}{\rightarrow}q para denotar q\in E(T(p,x))

Seja w uma string de L_{1}\cup L_{2}. Sem perda de generalidade, assumimos w\in L_{1}.

Seja w = x_{1}x_{2}\cdots x_{m} onde m\geq 0, x_{i}\in\Sigma

Uma vez que N_{1} aceita x_{1}x_{2}\cdots x_{m}, existem r_{0}, r_{1},\cdots r_{m}\in Q_{1} tais que

	q_{1}\stackrel{\epsilon , T_{1}}{\rightarrow}r_{0}\stackrel{x_{1} , T_{1}}{\rightarrow}r_{1}\stackrel{x_{2} , T_{1}}{\rightarrow}r_{2}\cdots r_{m-1}\stackrel{x_{m} , T_{1}}{\rightarrow}r_{m}, r_{m}\in A_{1}

Desde que T_{1}(q,x) = T(q,x)\ \forall q\in Q_{1}\forall x\in\Sigma

r_{0}\in E(T_{1}(q_{1},\epsilon ))\Rightarrow r_{0}\in E(T(q_{1},\epsilon ))
r_{1}\in E(T_{1}(r_{0},x_{1} ))\Rightarrow r_{1}\in E(T(r_{0},x_{1} ))
\vdots
r_{m}\in E(T_{1}(r_{m-1},x_{m} ))\Rightarrow r_{m}\in E(T(r_{m-1},x_{m} ))


Nós podemos, portanto, substituir T por T_{1} e rescrever o caminho acima como:


q_{1}\stackrel{\epsilon , T}{\rightarrow}r_{0}\stackrel{x_{1} , T}{\rightarrow}r_{1}\stackrel{x_{2} , T}{\rightarrow}r_{2}\cdots r_{m-1}\stackrel{x_{m} , T}{\rightarrow}r_{m}, r_{m}\in A_{1}\cup A_{2}, r_{0}, r_{1},\cdots r_{m}\in Q


Além disso,


\begin{array}{lcl}
T(q_{0}, \epsilon) = \{q_{1}, q_{2}\} & \Rightarrow & q_{1}\in T(q_{0}, \epsilon)\\
						\\ & \Rightarrow & q_{1}\in E(T(q_{0}, \epsilon))\\
						\\ & \Rightarrow & q_{0}\stackrel{\epsilon , T}{\rightarrow}q_{1}
\end{array}

e

q_{0}\stackrel{\epsilon , T}{\rightarrow}q_{1}\stackrel{\epsilon , T}{\rightarrow}r_{0}\Rightarrow q_{0}\stackrel{\epsilon , T}{\rightarrow}r_{0}


O caminho acima pode ser reescrito como:


q_{0}\stackrel{\epsilon , T}{\rightarrow}r_{0}\stackrel{x_{1} , T}{\rightarrow}r_{1}\stackrel{x_{2} , T}{\rightarrow}r_{2}\cdots r_{m-1}\stackrel{x_{m} , T}{\rightarrow}r_{m}, r_{m}\in A_{1}\cup A_{2}, r_{0}, r_{1},\cdots r_{m}\in Q


Portanto, N aceita x_{1}x_{2}\cdots x_{m} e a prova está concluída.


Nota: A ideia extraída desta prova matemática para construção de uma máquina para reconhecer L_{1}\cup L_{2} é criar um estado inicial e conectá-lo aos estados iniciais de L_{1} e L_{2} usando transições vazias (\epsilon).

Referências[editar | editar código-fonte]

  • Michael Sipser, Introduction to the Theory of Computation ISBN 0-534-94728-X. (Teorema 1.22, seção 1.2, pg. 59.)