Concatenação de linguagens regulares

Considere duas linguagens regulares L₁, L₂. Vamos demonstrar que a concatenação delas, L = L₁ ∘ L₂, também é uma linguagem regular.

O que é a concatenação

Concatenando as duas palavras “010” e “1111”, obtemos a palavra “0101111”. A concatenação de linguagens produz, assim, uma nova linguagem, que construímos concatenando cada palavra de uma linguagem com cada palavra da outra linguagem. A concatenação de duas palavras e de duas linguagens será representada por uma bolinha: ∘. Podemos, então, definir a concatenação das linguagens L₁ e L₂ assim:

$$L_1\circ L_2=\{a\circ b|a\in L_1,b\in L_2\}$$

Ideia da demonstração

Temos duas linguagens regulares L₁, L₂ e dois autômatos que aceitam essas linguagens:

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\\ A_2& =& ⟨Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2⟩\end{array}$$

Construímos um autômato não determinístico A = ⟨Q, Σ, δ, q, F⟩ que “contém em si” os dois autômatos A₁ e A₂. A ideia básica é que começamos a aceitar a palavra com o autômato A₁ e, quando o autômato A₁ chega a um estado final, tentamos ainda aceitar a parte restante da palavra com o autômato A₂. Se esse autômato também aceita a parte da palavra, então o autômato A aceita a palavra.

Exemplo

Considere este autômato A₁, que aceita as palavras não vazias compostas apenas de zeros e as palavras compostas de um 1 seguido apenas de zeros (1, 10, 100, …):

e considere também este autômato A₂, que aceita as palavras que terminam em 01:

Unimos os autômatos assim: de todos os estados finais do autômato A₁, acrescentamos transições ε para o estado inicial do autômato A₂ e, em seguida, transformamos os estados finais de A₁ em estados comuns. O estado inicial do novo autômato inteiro será o estado inicial do autômato A₁:

Como o autômato vai funcionar? Começamos simulando o funcionamento do autômato A₁. Se passarmos para um ex-estado final q₁ ou q₂, sabemos que o autômato A₁ aceita uma parte dessa palavra. Para que a palavra inteira faça parte da linguagem L₁ ∘ L₂, a parte restante da palavra deve ainda ser aceita pelo segundo autômato A₂ — por isso, de todos os ex-estados finais saem transições ε para o estado inicial original do autômato A₂.

Como exemplo, tome a palavra 0001. Ela pertence à concatenação das duas linguagens, porque a palavra pode surgir da concatenação das palavras 00 ∘ 01. Mas também pode surgir da concatenação das palavras 0 ∘ 001. No nosso autômato podemos simular os dois procedimentos. O autômato pode seguir por este caminho:

$$q_0{\to }^0{q}_1{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

Por esse caminho, o autômato primeiro “aceitaria” a parte 00 da palavra e depois a parte 01. Ou pode seguir por este caminho:

$$q_0{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

e o autômato “aceitaria”, então, primeiro a parte 0 da palavra e depois a parte 001. Nos dois casos, é claro, chegamos ao estado final p₂.

Procedimento formal

Mais uma vez: temos duas linguagens regulares L₁, L₂ e dois autômatos que aceitam essas linguagens:

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\\ A_2& =& ⟨Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2⟩\end{array}$$

Construímos o autômato não determinístico A = ⟨Q, Σ, δ, q, F⟩, para o qual vale:

• Q = Q₁ ∪ Q₂ (supomos, ao mesmo tempo, que Q₁ ∩ Q₂ = ∅)
• Σ= Σ₁ ∪ Σ₂
• q = q₀
• F = F₂

Construímos a função de transição δ aos poucos:

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& \text{se}& q\in Q_1\wedge q\notin F_1\\ {\delta }_1(q,a)& \text{se}& q\in F_1\wedge a\ne \epsilon \\ {\delta }_1(q,a)\cup \left\{p_0\right\}& \text{se}& q\in F_1\wedge a=\epsilon \\ {\delta }_2(q,a)& \text{se}& q\in Q_2\end{array}$$

Fontes

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools