Parte 6

Prévia do material em texto

Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Texto base 
6 
 
Teoria da Computação 
Ana Paula Ferreira da Rocha 
Resumo 
A semântica de não determinismo adotaremos é a usual no estudo de linguagens formais. 
No contexto da linguagem formal, a facilidade de não-determinística nem sempre 
aumenta o poder de reconhecimento da linguagem de uma classe de autômatos. Qualquer 
autômato finito não determinístico pode ser simulado por um autômato finito 
determinístico. 
Introdução 
 Abordaremos a teoria dos autômatos finitos não determinísticos e o conceito de 
equivalência entre autômatos e suas principais definições e aplicações. A importância 
destes conceitos para nossos estudos será aprimorar a base do raciocínio típico das 
linguagens formais. 
 
 
6.1. Autômato finito não determinístico 
O não determinismo é uma importante generalização dos modelos de máquinas, sendo de 
fundamental importância no estudo dos modelos para concorrência, na teoria da 
computação e nas linguagens formais. 
A semântica de não determinismo adotada é a usual no estudo das linguagens formais no 
sentido em que objetiva determinar a capacidade de reconhecer linguagens e de 
solucionar problemas. No contexto das linguagens formais nem sempre a facilidade de 
não determinismo aumenta o poder de reconhecimento de linguagens de uma classe de 
autômatos. Sendo assim qualquer autômato finito não determinístico pode ser simulado 
por um autômato finito determinístico. 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
A facilidade de tal determinismo para autômatos finitos é expressa no programa, que é 
uma função tal que para o estado corrente e o símbolo lido na entrada, determina 
aleatoriamente um estado de um conjunto de estados alternativos. 
Sendo assim a cada transição não determinista novos caminhos alternativos são possíveis 
definindo uma árvore de opções. Uma entrada é aceita se pelo menos um dos caminhos 
alternativos aceita a entrada, mesmo que os demais não aceitem. Assim, para um 
autômato finito não determinístico visto como uma máquina composta por fita, unidade 
de controle e programa, define-se uma semântica que assume um conjunto de estados 
alternativos, como se houvesse uma multiplicação da unidade de controle, sendo uma 
para cada alternativa, processando independentemente sem compartilhar recursos com as 
demais. Assim o processamento de um caminho não influi no estado, no símbolo lido e 
na posição da cabeça dos demais caminhos alternativos e todos os caminhos alternativos 
são investigados simultaneamente. 
Um AFN (autômato finito não determinístico) M é uma 5-upla ordenada: 
 M = (∑, Q, 𝜹, q0, F) 
Onde: 
• ∑ é um alfabeto de símbolos de entrada; 
• Q é um conjunto de estados possíveis do autômato o qual é finito; 
• 𝜹 é uma função programa, ou ainda função de transição: 
• 𝜹: Q x ∑ ⟶ 2Q 
A qual é uma função total, assim para um estado p e um símbolo a: 
• 𝜹(p, a) = {q1, q2, ..., qn} 
É uma transição do autômato. 
• q0 é um elemento distinguido de Q, denominado estado inicial; 
• F é um subconjunto de Q, denominado conjunto de estados finais. 
Portanto executando-se pela função programa 𝜹 as componentes ∑, Q, q0 e F são como 
na definição do autômato finito determinístico. Se para um estado p e um símbolo a ocorre 
que 𝜹(p, a) = ∅, então afirma-se que a transição é indefinida para o par (p, a) e, portanto, 
o autômato para rejeitado a entrada. A representação da função programa como um 
diagrama é similar à do autômato finito determinístico, a representação diagramática de 
uma transição do tipo: 
 𝜹(p, a) = {q1, q2, ..., qn} 
Resulta em diversas arestas etiquetadas por a, com origem em p, e com destino em cada 
estado q1, q2, ..., qn, mostrando os diversos caminhos alternativos, conforme figura 
abaixo: 
 
Figura 1.1 – Diagrama AFN - transição 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
 
Fonte: Paulo Blauth Menezes, 2011. 
 
Semelhante aos autômatos finitos determinísticos a computação de um autômato finito 
não determinístico, para uma palavra de entrada w, consiste na sucessiva aplicação da 
função programa para cada símbolo de w (da esquerda para a direita) até ocorrer uma 
condição de parada. Como cada transição de autômato não determinístico resulta em um 
conjunto de estados é necessário estender a definição da função programa, usando como 
argumento um conjunto finito de estados e uma palavra. 
 
Função programa, função estendida, computação 
Seja M = (∑, Q, 𝜹, q0, F) um autômato finito não determinístico, a função programa 
estendida ou computação de M, representado por: 
 𝛿*: 2Q x ∑* ⟶ 2Q 
É a função programa 𝜹: Q x ∑ ⟶ 2Q estendida para palavras e conjuntos de estados 
definida como segue: 
𝜹*(P, 𝜺) = P 
𝜹*(P, aw) = 𝜹*(∪q∈P 𝜹(q, a), w) 
A função programa estendida consiste na sucessiva aplicação da função programa a cada 
símbolo da palavra, a partir de um conjunto de estados. Devemos observar que se a 
entrada for vazia o autômato fica parado nos estados correntes. 
A transição estendida a um conjunto de estados é a união dos resultados da função 
programa aplicada a cada estado alternativo. Assim para um conjunto de estados {q1, q2, 
..., qn} e para o símbolo a: 
 𝜹*({q1, q2, ..., qn}, a) = 𝜹(q1, a) ∪...∪ 𝜹(qn, a) 
A parada do processamento de um autômato finito não determinístico para uma entrada 
w pode ser de duas maneiras: 
• Aceita a entrada w, depois de processar o último símbolo da fita existe pelo menos 
um estado final pertencente ao conjunto de estados alternativos atingidos; 
• Rejeita a entrada w, neste caso são duas as possibilidades: 
a) Depois de processar o último símbolo da fita todos os estados alternativos 
atingidos são não finais; 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
b) Em algum momento no decorrer do processamento de w o conjunto de estados 
alternativos atingido é vazio, assim o autômato para por definição. 
 
Linguagem aceita, linguagem rejeitada 
Seja M = (∑, Q, 𝜹, q0, F) um autônomo finito não determinístico a linguagem aceita ou 
linguagem reconhecida por M, é representada por: 
 ACEITA(M) ou L(M) 
É o conjunto de todas as palavras pertencentes a ∑* tais que existe pelo menos um 
caminho alternativo que aceita a palavra partindo de {q0}: 
 ACEITA(M) = {w | 𝜹*({q0}, w) ∩ F ≠ ∅} 
Em contrapartida a linguagem rejeitada por M é representada por: 
 REJEITA(M) 
É o conjunto de todas as palavras pertencentes a ∑* rejeitada por todos os caminhos 
alternativos de M partindo de {q0}: 
 REJEITA(M) = {w | 𝜹*({q0}, w) ∩ F ≠ ∅} 
 
Autômato finito não determinístico: aa ou bb como subpalavra 
Consideraremos a seguinte linguagem sobre o alfabeto {a, b}: 
 L5 = {w | w possui aa ou bb como subpalavra} 
O autômato finito não determinístico: 
 M5 = ({a, b}, {q0, q1, q2, qf}, 𝜹5, q0, {qf}) 
Onde 𝜹5 é dada, tal qual ACEITA(M5) = L5: 
 
Tabela 1.1 – Função programa AFN – sequência de dois símbolos iguais 
𝜹5 a b 
qo {q0, q1} {q0, q2} 
q1 {qf} ∅ 
q2 ∅ {qf} 
qf {qf} {qf} 
Fonte: Paulo Blauth Menezes, 2011. 
O autômato M5 pode ser representado pelo diagrama: 
 
Figura 1.2 – Diagrama AFN – sequência de símbolos iguais 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
 
 
Fonte: Paulo Blauth Menezes, 2011. 
 
O algoritmo apresentado realiza uma varredura sobre a palavra de entrada, a cada 
ocorrência de a, e respectivamente b, uma alternativa é iniciada para verificar se símbolo 
seguinte é a, e respectivamente b, possuindo três alternativas de processamento: 
• O ciclo em qo realiza uma varredura em toda a entrada; 
• O caminho q0/q1/qf garante a ocorrência de aa; 
• O caminho q0/q2/qf garante a ocorrência de bb. 
A computação abaa a partir do conjunto de estados {q0} é como segue: 
𝜹*({qo}, abaa) – função estendiasobre abaa 
𝜹*(𝜹(q0, a), baa) – processa abaa 
𝜹*({q0, q1}, baa) – função estendida sobre baa 
𝜹*(𝜹(q0, b) ∪ 𝜹(q1, b), aa) – processa baa 
𝜹*({q0, q2} ∪ ∅, aa) 
𝜹*({q0, q2}, aa) – função estendida sobre aa 
𝜹*(𝜹(q0, a) ∪ 𝜹(q2, a), a) – processa aa 
𝜹*({q0, q1} ∪ ∅, a) 
𝜹*({q0, q1}, a) – função estendida sobre a 
𝜹*(𝜹(q0, a) ∪ 𝜹(q1, a), 𝜺) – processa a 
𝜹*({q0, q1} ∪ {qf}, 𝜺) 
𝜹*({q0, q1, qf}, 𝜺) = {q0, q1, qf} – função estendida sobre 𝜺: fim da indução 
Portanto a palavra é aceita pois {q0, q1, qf} ∩ F = {qf} ≠ ∅. 
 
Autômato finito não determinístico: aaa como sufixo 
Considere a seguinte linguagem sobre o alfabeto {a, b}: 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
 L6 = {w | w possui aaa como sufixo} 
O autômato finito não determinístico: 
 M6 = ({a, b}, {q0, q1, q2, qf}, 𝜹6, q0, {qf}) 
É tal que ACEITA(M6) = L6: 
 
Figura 1.3 – Diagrama AFN – aaa como sufixo 
 
Fonte: Paulo Blauth Menezes, 2011. 
 
A computação da palavra baa a partir do conjunto de estados {q0} é como segue: 
𝜹*({q0}, baa) – função estendida sobre baa 
𝜹*(𝜹(q0, b), aa) – processa baa 
𝜹*({q0}, aa) – função estendida sobre aa 
𝜹*(𝜹(q0, a), a) – processa aa 
𝜹*({q0, q1}, a) – função estendida sobre a 
𝜹*(𝜹(q0, a) ∪ 𝜹(q1, a), 𝜺) – processa a 
𝜹*({q0, q1} ∪ {q2}, 𝜺) 
𝜹*({q0, q1, q2}, 𝜺) = {q0, q1, q2} – função estendida sobre 𝜺: fim da indução 
Portanto a palavra é rejeitada pois {q0, q1, q2} ∩ F = ∅. 
Embora a facilidade de não determinismo seja, aparentemente, um significativo 
acréscimo ao autômato finito, na realidade não aumenta seu poder computacional. Assim 
para cada AFN é possível construir um AFD equivalente que realiza as mesmas 
computações o contrário também é verdadeiro. 
 
Você sabia? 
Vamos aprofundar o conhecimento sobre Autômato Finito Não Determinístico? Assista 
ao vídeo Autômato Finito Não Determinístico – com Prof. José Rui. Disponível em: 
< https://www.youtube.com/watch?v=hq41dwJFjpw>. Acesso em: 27 abr. 2023. 
 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
6.2. Equivalência entre autômatos 
Autômatos finitos determinísticos e não determinísticos reconhecem a mesma classe de 
linguagens, tal equivalência é tanto surpreendente quanto útil. Surpreendente porque 
AFN’s parecem ter mais poder que AFD’s, portanto poderíamos esperar que AFN’s 
reconhecessem mais linguagens, é útil porque descrever um AFN para uma dada 
linguagem, às vezes, é muito mais fácil que descrever um AFD para a mesma linguagem. 
Digamos que duas máquinas são equivalentes se elas reconhecem a mesma linguagem. 
 
Prova – por indução 
A prova consiste em mostrar que a partir de um AFN M qualquer, é possível construir 
um AFD MD que realiza as mesmas computações a ideia central do algoritmo é a 
construção de estados de MD que simulem as diversas combinações de estados 
alternativos de M. 
Seja M = (∑, Q, 𝜹, q0, F) um AFN qualquer: 
 MD = (∑, QD, 𝜹D, <q0>, FD) 
Um AFD construído a partir de M: 
• QD é o conjunto construído a partir de todas as combinações, sem repetições, de 
estados de Q, cada estado de QD é representado por: 
 <q1q2...qn> 
Onde qi pertence a Q, para i em {1, 2, ..., n}, portanto um estado de MD representa uma 
imagem de todos os estados alternativos de M. É importante observar que a ordem dos 
elementos não distingue mais combinações, por exemplo <quqv> = <qvqu>. 
• 𝜹D: QD x ∑ ⟶ QD é tal que: 
𝜹(<q1 ... qn>, a) = <p1 ... pm> se e somente se 𝜹*({q1, ..., qn}, a) = {p1, ..., pm} em 
particular: 
𝜹D (<q1 ... qn>, a) é indefinida se e somente se 𝜹*({q1, ..., qn}, a) = ∅ 
• <q0> é o estado inicial. 
• FD é o conjunto de todos os estados <q1q2...qn> pertencentes a QD tal que que 
alguma componente qi pertence a F, para i em {1, 2, ..., n}. 
A demonstração de que o AFD MD de fato simula exatamente as computações do AFN 
M é por indução no tamanho da palavra, deve-se mostrar que, suponha w uma palavra 
qualquer de ∑*: 
 𝜹D*(<q0>, w) = <q1 ... qu> se e somente se 𝜹*({q0}, w) = {q1, ..., qu} 
 
Base de indução 
Seja w tal que | w | = 0, portanto w = 𝜺: 
 𝜹D*(<q0>, 𝜺) = <q0> se e somente se 𝜹*({q0}, 𝜺) = {q0} 
O que é verdadeiro por definição de função programa estendida. 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Hipótese de indução 
Seja w tal que | w | = n e n ≥ 1, suponha verdadeiro que: 
𝜹D*(<q0>, w) = <q1 ... qu> se e somente se 𝜹*({q0}, w) = {q1, ..., qu} 
 
Passo de indução 
Seja w tal que | wa | = n + 1 e n ≥ 1, então: 
𝜹D*(<q0>, wa) = <p1 ... pv> se e somente se 𝜹*({q0}, wa) = {p1, ..., pv} 
O que equivale por hipótese de indução: 
𝜹D (<q1 ... qu>, a) = <p1 ... pv> se e somente se 𝜹*({q1, ..., qu}, a) = {p1, ..., pv} 
O que é verdadeiro por definição de 𝜹D. 
Logo MD simula M para qualquer entrada w pertencente a ∑*, sendo assim uma 
linguagem aceita por um autômato finito não determinístico é uma linguagem regular. 
 
Determinismo x Não determinismo 
Muitas vezes é mais fácil desenvolver um autômato finito não determinístico do que um 
determinístico. Um exemplo interessante é desenvolver um autômato que aceita a 
seguinte linguagem sobre ∑ = {a, b}: 
 {w | o quinto símbolo da direita para a esquerda de w é a} 
A solução determinista não é trivial e resulta em um número relativamente grande de 
estados. Entretanto uma solução não determinista é bem simples e necessita de poucos 
estados. Assim em muitos casos para construir um autômato finito determinístico é 
preferível desenvolver inicialmente uma solução não determinista e sobre esta solução 
aplicar o algoritmo apresentado na prova por indução. 
 
Construção de um AFD a partir de um AFN 
Considere o AFN, um autômato finito não determinístico aaa como sufixo: 
 M6 = ({a, b}, {q0, q1, q2, qf}, 𝜹6, q0, {qf}) 
O correspondente AFD: 
 M6D = ({a, b}, QD, 𝜹6D, <q0>, {qf}) 
Construído conforme a prova de equivalência entre AFD e AFN, tal que: 
 QD = {<q0>, <q1>, <q2>, <qf>, <q0q1>, <q0q2>, ..., <q0q1q2qf>} 
 FD = {<qf>, <q0qf>, <q1qf>, ..., <q0q1q2qf>} 
 𝜹6D = é dada pela, conforme tabela a seguir na qual são explicitados apenas os 
estados para os quais a função programa é definida: 
 
Tabela 1.2 – Função programa AFD a partir de um AFN 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
𝜹6D a b 
<q0> <q0q1> <q0> 
<q0q1> <q0q1q2> <q0> 
<q0q1q2> <q0q1q2qf> <q0> 
<q0q1q2qf> <q0q1q2qf> <q0> 
Fonte: Paulo Blauth Menezes, 2011. 
 
M6D, é ilustrado na figura abaixo, por simplicidade os estados <q0>, <q0q1>, <q0q1q2> 
e <q0q1q2qf> foram renomeados respectivamente para p0, p1, p2 e pf: 
 
Figura 1.4 – Diagrama AFD construído a partir do AFN 
 
 
Fonte: Paulo Blauth Menezes, 2011. 
 
 
Você sabia? 
Vamos aprofundar o conhecimento sobre Equivalência entre Autômatos? Assista ao 
vídeo Equivalência AFN x AFD. Disponível em: 
< https://www.youtube.com/watch?v=iWfqS73d6tU>. Acesso em: 27 abr. 2023. 
 
 
 
 
Considerações finais 
 Como vimos a semântica do não determinismo adotada é a usual no estudo das 
linguagens formais no sentido de que visa determinar o reconhecimento da linguagem e 
a capacidade de resolução de problemas. No contexto de linguagens formais, a facilidade 
de indeterminação nem sempre aumenta a consciência de linguagem das classes de 
autômatos. Consequentemente, um autômato finito não determinístico pode ser modelado 
por um autômato finito determinístico. Essa facilidade determinística de autômatos finitos 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
é expressa programaticamente. Esta é uma função que determina um estado aleatório do 
estado atual e um conjunto de estados alternativos para os emblemas lidos da entrada. 
Uma vez que autômatos finitos determinísticos e não determinísticos confessam a mesma 
classe de linguagens, tal equivalência ésurpreendente e útil. Surpreendente porque os 
AFN’s parecem ter mais poder do que os AFD’s, então seria de se esperar que os AFN’s 
confessam mais idiomas, isso é útil porque descrever um AFN para um determinado 
idioma às vezes é muito mais fácil do que descrever um AFD para o mesmo idioma. 
Digamos que duas máquinas sejam equivalentes se reconhecerem a mesma linguagem. 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Referências 
DIVERIO, Tiarajú Asmuz; MENEZES, Paulo Blauth. Teoria da Computação: 
máquinas universais e computabilidade. Porto Alegre: Bookman, 2011. 
MENEZES, Paulo Blauth. Linguagens Formais e Autômatos. 6. ed. Porto Alegre: 
Bookman, 2011. 
SIPSER, Michael. Introdução à Teoria da Computação. 2. ed. São Paulo: Cengage 
Learning, 2007.