07 - Equivalência AF e GR

07 · Equivalência entre Autômatos Finitos e Gramáticas Regulares

Resumo em 30 segundos

Estado vira não terminal e transição vira produção. AF → GR: cada $T(B,a)=C$ vira $B\to aC$ (e também $B\to a$ se $C$ é final). GR → AF: cada $B\to aC$ vira $T(B,a)=C$, e cada $B\to a$ leva a um novo estado final $Z$. As duas conversões mostram que gramáticas regulares e autômatos finitos descrevem exatamente as mesmas linguagens.

Anterior: 06 - Equivalência AFD e AFND · Voltar ao mapa

---

A analogia que resolve tudo

Autômato	Gramática regular
estado $B$	não terminal $B$
estado inicial $i$	símbolo inicial $S$
transição $B\stackrel{a}{\to }C$	produção $B\to aC$
“chegar em final e parar”	produção que termina só com terminal: $B\to a$
inicial é final (aceita $\epsilon$)	$S\to \epsilon$

Cada passo de derivação $\cdots \Rightarrow w_1\dots w_{k}B\Rightarrow w_1\dots w_{k}aC$ corresponde a ler a e ir de $B$ para $C$. A forma sentencial de uma gramática regular sempre tem um único não terminal, no fim, e ele faz o papel do estado atual.

AF para GR

Slides 3 e 4. Dado $M=(K,V_t,T,i,F)$, a gramática $G=(V_n,V_t,S,P)$ é:

• $V_t$: o mesmo alfabeto.
• $S=i$.
• $V_n$: os estados. Estados finais sem nenhuma transição de saída podem ser descartados (é o que o slide chama de “F não aceita símbolos”), porque nunca aparecem do lado direito como $aC$.
• $P$, para cada transição $T(B,a)=C$:

Situação	Produções
$C\notin F$	$B\to aC$
$C\in F$ e $C$ não tem transições de saída	$B\to a$
$C\in F$ e $C$ tem transições de saída	$B\to aC\mid a$
$i\in F$	acrescentar $S\to \epsilon$

O resultado é uma gramática linear à direita (ver aula 03, slide 14).

Exemplo dos slides 5 e 6

T	0	1
→ S	{A}	∅
A	{A, B}	{S}
* B	{S}	{A}

$B$ é final e tem saídas, então fica em $V_n$ e toda transição que chega em $B$ gera as duas versões.

Transição	Produções
$T(S,0)=\{A\}$	$S\to 0A$
$T(A,0)=\{A,B\}$	$A\to 0A\mid 0B\mid 0$
$T(A,1)=\{S\}$	$A\to 1S$
$T(B,0)=\{S\}$	$B\to 0S$
$T(B,1)=\{A\}$	$B\to 1A$

Conferi por programa que essa gramática gera exatamente as palavras aceitas pelo autômato (até tamanho 9).

A conversão funciona para AFND também

O exemplo do slide 5 tem $T(A,0)=\{A,B\}$, então é um AFND. Não precisa determinizar antes: cada destino do conjunto vira uma produção.

GR para AF

Slides 7 e 8. Dada $G=(V_n,V_t,S,P)$, o autômato $M=(K,V_t,T,i,F)$ é:

• $K=V_n\cup \{Z\}$, onde $Z$ é um estado novo.
• $i=S$.
• $F=\{Z\}$ ($Z$ não tem transições de saída).
• Para cada produção:

Produção	Transição
$B\to aC$	$T(B,a)$ inclui $C$
$B\to a$	$T(B,a)$ inclui $Z$
$S\to \epsilon$	$S$ também entra em $F$

Em geral o resultado é um AFND (quando há $B\to aC$ e $B\to a$ com o mesmo $a$, por exemplo). Se precisar de um AFD, aplique a construção de subconjuntos.

Exemplo dos slides 9 e 10

$P=\{S\to 0A\mid 1B,A\to 0A\mid 1B\mid 0,B\to 0A\mid 1S\mid 1\}$

T	0	1
→ S	{A}	{B}
A	{A, Z}	{B}
B	{A}	{S, Z}
* Z	∅	∅

$T(A,0)=\{A,Z\}$ vem de $A\to 0A$ e $A\to 0$: não determinismo. Conferido por programa até tamanho 9.

flowchart LR
  AF[Autômato Finito] -- "estados viram não terminais<br/>transições viram produções" --> GR[Gramática Regular]
  GR -- "não terminais viram estados + Z<br/>produções viram transições" --> AFND[AFND]
  AFND -- "construção de subconjuntos<br/>(aula 06)" --> AFD[AFD]
  AFD --> AF

Slides 11 e 12: exercícios

Todas as respostas foram conferidas por programa: gerei as palavras de cada gramática e comparei com as aceitas pelo autômato correspondente.

Exercício 1: gramática do autômato da esquerda

Transições lidas do slide ampliado: $q_0$ laço 1; $q_0\stackrel{0}{\to }{q}_1$; $q_1$ laço 1; $q_1\stackrel{1}{\to }{q}_3$; $q_1\stackrel{0}{\to }{q}_2$; $q_2\stackrel{1}{\to }{q}_1$; $q_2\stackrel{0}{\to }{q}_3$. Finais: $q_2$ e $q_3$. ($q_1$ com 1 vai para $\{q_1,q_3\}$: é AFND.)

Renomeando $S=q_0$, $A=q_1$, $B=q_2$ ($q_3$ é final sem saída, então não vira não terminal):

$S\to 1S\mid 0AA\to 1A\mid 1\mid 0B\mid 0B\to 1A\mid 0$

Linguagem (bônus, conferida até tamanho 12): $1^{\ast }0(1\mid 01{)}^{\ast }(0\mid 1\mid 00)$.

Exercício 2: gramática do autômato da direita

Transições: $q_0$ laço 0 e 1; $q_0\stackrel{0}{\to }{q}_1$; $q_1$ laço 1; $q_1\stackrel{0}{\to }{q}_2$; $q_2$ laço 0; $q_2\stackrel{1}{\to }{q}_1$. Final: $q_2$ (tem saídas).

Com $S=q_0$, $A=q_1$, $B=q_2$:

$S\to 0S\mid 1S\mid 0AA\to 1A\mid 0B\mid 0B\to 0B\mid 0\mid 1A$

Linguagem (bônus, conferida até tamanho 11): palavras com pelo menos dois 0 que terminam em 0.

Exercício 3: autômato da gramática com S, A, B, C

$P=\{S\to aA\mid bB\mid C,A\to aA\mid bC,B\to aC\mid bB,C\to aS\mid bS\mid a\mid b\}$

Atenção: $S\to C$ é uma produção unitária (lado direito é só um não terminal). Ela não se encaixa em $B\to aC$ nem $B\to a$, então a regra de conversão dos slides não se aplica direto. Primeiro elimine: troque $S\to C$ pelas produções de $C$:

$S\to aA\mid bB\mid aS\mid bS\mid a\mid b$

Conferi que a linguagem não muda com essa troca. Agora converta:

T	a	b
→ S	{A, S, Z}	{B, S, Z}
A	{A}	{C}
B	{C}	{B}
C	{S, Z}	{S, Z}
* Z	∅	∅

Curiosidade: essa gramática gera todas as palavras não vazias, $(a|b{)}^{+}$, porque $S\to aS\mid bS\mid a\mid b$ sozinho já gera tudo. $A$, $B$ e $C$ acabam sendo redundantes. Conferido até tamanho 9.

Exercício 4: autômato da gramática com S, A, B

$P=\{S\to aA\mid bB,A\to aA\mid bS\mid a,B\to aS\mid bB\mid b\}$

T	a	b
→ S	{A}	{B}
A	{A, Z}	{S}
B	{S}	{B, Z}
* Z	∅	∅

Linguagem (bônus, conferida até tamanho 13): $(a^{+}b\mid b^{+}a{)}^{\ast }(a{a}^{+}\mid b{b}^{+})$. Em palavras: blocos do tipo “vários a e um b” ou “vários b e um a”, terminando com um bloco de pelo menos dois símbolos iguais.

---

Visão geral: tudo é a mesma classe

Com as aulas 03b, 04, 05, 06 e 07, fecha-se o quadro das linguagens regulares:

flowchart LR
  ER[Expressão Regular] <-->|livros, seção 3.6| AFND
  AFND <-->|aula 06| AFD
  AFD <-->|aula 07| GR[Gramática Regular]
  AFND <-->|aula 07| GR

A conversão ER ↔ autômato não está nestes slides; os livros mostram (Ramos, seção 3.6).

Aprofundamento com os livros

Páginas das edições da sua pasta: Menezes 3ª edição (2000) e Ramos, José Neto e Vega (Bookman).

A ideia central, nas palavras do Ramos (p. 203)

Não é só o símbolo inicial que gera uma linguagem: cada não terminal $X$ gera a sua, $L(X)=\{w\mid X{\Rightarrow }^{\ast }w\}$. Do mesmo jeito, cada estado $X$ aceita uma linguagem: as palavras que levam de $X$ até um estado final. A conversão só faz esses dois coincidirem. Uma produção $X\to aY$ passa a significar “a linguagem de $X$ é a seguido da linguagem de $Y$”, que é exatamente o que a transição $X\stackrel{a}{\to }Y$ diz.

O Ramos ainda observa que o número de passos bate: para gerar uma palavra de $n$ símbolos, a gramática usa uma forma sentencial a mais do que o número de configurações do autômato (p. 204 e 206).

GR para AF nos livros: regras com ε

Os livros aceitam dois tipos de produção que os slides não tratam, e convertem os dois com transições vazias:

Produção	Slides	Menezes (Teorema 2.18, p. 57)	Ramos (Algoritmo 3.14, p. 202 e 203)
$X\to aY$	$T(X,a)\ni Y$	igual	igual
$X\to a$	$T(X,a)\ni Z$	$\delta (X,a)=q_f$	$(X,a)\to Z$
$X\to Y$ (unitária)	não trata	$\delta (X,\epsilon )=Y$	$(X,\epsilon )\to Y$
$X\to \epsilon$	só $S\to \epsilon$ (inicial vira final)	$\delta (X,\epsilon )=q_f$	$(X,\epsilon )\to Z$

No Ramos, o autômato resultante tem $|N|+1$ estados e exatamente uma transição por produção.

O exercício 3 do slide 12, do jeito do Ramos

A produção unitária $S\to C$ que eu eliminei na resolução acima pode ser convertida direto numa transição vazia $S\stackrel{\epsilon }{\to }C$:

Conferi por programa que esse autômato com $\epsilon$ aceita exatamente $(a\mid b{)}^{+}$, igual à versão sem a produção unitária. As duas resoluções estão certas; use a que o professor preferir.

Menezes, Exemplo 16 (p. 58 e 59)

A gramática $S\to aA$, $A\to bB\mid \epsilon$, $B\to aA$ gera $a(ba{)}^{\ast }$. A regra $A\to \epsilon$ vira uma transição vazia de $A$ para o estado final:

Conferido por programa.

AF para GR nos livros: estados finais viram regras vazias

Os livros usam uma construção um pouco diferente da dos slides:

	Slides	Menezes (Teorema 2.19, p. 59)	Ramos (Algoritmo 3.15, p. 204 e 205)
Transição $T(X,a)=Y$	$X\to aY$, e também $X\to a$ se $Y$ é final	$X\to aY$	$X\to aY$
Estado final $X$	não gera regra própria	$X\to \epsilon$	$X\to \epsilon$
Símbolo inicial	o próprio estado inicial	um $S$ novo com $S\to q_0$	o próprio estado inicial
Transição vazia $T(X,\epsilon )=Y$	não trata	(parte de um AFD)	$X\to Y$

Com a regra dos livros, o exemplo do slide 5 fica assim: $S\to 0A$, $A\to 0A\mid 0B\mid 1S$, $B\to 0S\mid 1A\mid \epsilon$. Conferi por programa que gera a mesma linguagem que a gramática do slide 6.

Qual usar?

A regra dos slides evita produções vazias (útil se o professor exigir a forma $A\to aB\mid a$ do slide 13 da aula 03). A dos livros é mais mecânica: uma produção por transição e uma $X\to \epsilon$ por estado final, com $|P|=|T|+|F|$ no Ramos. As duas geram gramáticas equivalentes.

Mais de um caminho, mais de uma derivação (Ramos, Exemplo 3.38, p. 205 e 206)

Quando o autômato é não determinístico, uma palavra pode ser aceita por dois caminhos diferentes. Cada caminho corresponde a uma derivação diferente na gramática gerada. É a primeira aparição, em versão regular, da ideia de ambiguidade que aparece com força nas gramáticas livres de contexto.

O quadro completo das conversões (Menezes, Figura 2.23, p. 61)

O Menezes resume todas as traduções entre formalismos regulares num diagrama. Com as aulas até aqui mais os complementos dos livros:

flowchart LR
  ER[Expressão regular] -->|"Teorema 2.13"| AFE[AF com ε]
  AFE -->|"Teorema 2.11"| AFN[AFND]
  AFN -->|"Teorema 2.7 · aula 06"| AFD
  AFD -->|"Teorema 2.19 · aula 07"| GR[Gramática regular]
  GR -->|"Teorema 2.18 · aula 07"| AFE
  AFD -.->|"Teorema 2.14 (sem prova no Menezes; Ramos Alg. 3.17)"| ER

Os números são dos teoremas do Menezes. O exercício 2.8 do livro (p. 81) pede exatamente para percorrer esse caminho: partir de uma ER e chegar a uma gramática regular passando por AF com ε, AFND e AFD.

Para aprofundar nos livros

Onde ler (páginas das edições da sua pasta)

• Menezes (3ª ed.): 2.6 Gramática Regular, Teoremas 2.18 e 2.19 com os Exemplos 16 e 17, p. 57 a 60; exercícios 2.8 e 2.12, p. 81.
• Ramos, José Neto e Vega: 3.5 Gramáticas Regulares e Autômatos Finitos, p. 202 a 206; 3.4 Gramáticas Regulares e Conjuntos Regulares, p. 192 a 202.

Relacionadas: 03 - Gramáticas Regulares · 06 - Equivalência AFD e AFND · Glossário · Flashcards