Parte 5

Prévia do material em texto

Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Texto base 
5 
 
Teoria da Computação 
Ana Paula Ferreira da Rocha 
Resumo 
O autômato executa quando receber sequências de dados de entrada em intervalos de 
tempo discretos. Contém um subconjunto de estados de autômato que é definido como 
um conjunto de estados de aceitação. Se o status final aceitar, o autômato aceitou essa 
palavra. O conjunto de todas as palavras aceitas pelo autômato é chamado de linguagem 
reconhecida pelo autômato. Um subconjunto da linguagem do autômato é a linguagem 
que o autômato reconhece. 
Introdução 
 Abordaremos a teoria dos autômatos e o conceito de autômatos finitos 
determinísticos e suas principais definições e aplicações. A importância dos autômatos 
para a Teoria da Computação que é a base das máquinas universais bem como demais 
teorias que veremos no decorrer de nosso curso. 
 
 
5.1. Autômatos 
Segundo Sipser (2007) podemos definir a teoria dos autômatos como o estudo das 
máquinas abstratas também chamadas de autômatos, sendo de grande auxílio na resolução 
de problemas computacionais por facilitar tais resoluções com a utilização dos autômatos. 
O autômato executa quando receber sequências (separadas) de dados de entrada em 
intervalos de tempo discretos. O autômato processa a entrada de um conjunto de 
caracteres ou letras chamados alfabeto. Os símbolos que o autômato aceita como entrada 
em qualquer etapa (ou etapas) são sequências de símbolos conhecidas como palavras. Um 
autômato consiste em um conjunto finito de estados. A cada momento de sua execução, 
o autômato entra em um de seus estados. Quando uma nova entrada é recebida, ela faz a 
transição para outro estado (ou transições) com base em uma função que recebe o estado 
atual e o código como parâmetros. Essa função é chamada de função de transmutação. O 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
autômato lê os símbolos da palavra de entrada um após o outro e se move de estado para 
estado de acordo com a função de transição até que a palavra seja completamente lida. 
Uma vez lida a palavra de entrada, diz-se que o autômato para. O estado em que o 
autômato para é chamado de estado final. Dependendo do estado final, o controlador pode 
aceitar ou rejeitar uma palavra de entrada. Contém um subconjunto de estados de 
autômato que é definido como um conjunto de estados de aceitação. Se o status final 
aceitar, o autômato aceitou essa palavra. Ocorrência contrário, a palavra será rejeitada. O 
conjunto de todas as palavras aceitas pelo autômato é chamado de linguagem reconhecida 
pelo autômato. Um subconjunto da linguagem do autômato é a linguagem que o autômato 
reconhece. 
Simplificando, um autômato é um objeto matemático que recebe palavras como entrada 
e decide aceitá-las ou não. Uma vez que todos os problemas computacionais podem ser 
reduzidos ao problema de aceitação / rejeição de palavras (todas as instâncias do problema 
podem ser representadas por um tamanho finito de símbolos), com isso podemos afirmar 
que a teoria dos autômatos desempenha um importante papel na teoria da computação. 
5.2. Autômato finito 
Segundo Menezes (2011) podemos definir autômato finito como um sistema de estados 
finitos, isto é que possui um número finito e predefinido de estados, constituindo um 
modelo computacional sequencial comum em vários estudos formais e teóricos da 
computação, onde destacamos as linguagens formais, os compiladores, a semântica 
formal e os modelos para concorrência. O autômato finito é um formalismo que além de 
operacional, também é reconhecedor e divide-se em: 
• Determinístico – para o estado corrente e o símbolo lido da entrada o sistema 
assume um único estado determinado; 
• Não determinístico – para o estado corrente e o símbolo lido da entrada o sistema 
assume um estado pertencente a um conjunto de estados alternativos; 
• Com movimentos vazios – para o estado corrente, apesar de ler um símbolo ou 
não da entrada, o sistema assume um estado pertencente a um conjunto de estados 
alternativos sendo assim não determinístico. O movimento é tido como 
movimento vazio se o sistema muda de estado sem um correspondente leitura de 
símbolo. Estes movimentos vazios podem referir-se a transições encapsuladas 
onde ao serem executadas por uma eventual mudança de estado, não teremos 
nenhuma outra observação de forma parecida com a ideia de encapsulamento nas 
linguagens orientadas a objetos. 
Prova-se desta forma, com as descrições acima, que as três divisões do autômato se 
tornam semelhantes em termos de poder computacional. Um autômato finito pode ser 
visto como uma máquina constituída, em suma, de três partes: 
• Fita – dispositivo de entrada que contém a informação a ser processada; 
• Unidade de controle – indica o estado corrente da máquina, possui uma unidade 
de leitura, chamada de cabeça da fita, que acessa uma célula da fita de cada vez e 
sua movimentação é somente para a direita; 
• Programa, função programa ou função de transição – comanda as leituras e define 
o estado da máquina. 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
A fita é finita, independentemente da direção, sendo dividida em células onde cada uma 
armazena um símbolo. Os símbolos pertencem a um alfabeto de entrada, não sendo 
possível gravar sobre a fita, e não possuímos memória auxiliar. Sendo assim a palavra a 
ser processada ocupa toda a fita. 
A unidade de controle possui um número finito e predefinido de estados, por esta razão 
chama-se controle finito. A unidade de controle lê um símbolo da fita de cada vez, após 
a leitura a cabeça da fita move-se uma célula à direita. A cabeça da fita inicia a leitura 
posicionada na célula mais à esquerda da fita: 
 
Figura 1.1 – Autômato finito como uma máquina com controle finito 
 
Fonte: Paulo Blauth Menezes, 2011. 
 
Já o programa é uma função que dependendo do estado corrente e do símbolo lido, 
determina o novo estado do autômato. 
Você sabia? 
Vamos aprofundar o conhecimento sobre Autômato Finito? Assista ao vídeo 
Expressões regulares e Autômatos finitos – Canal Computação – UFC Crateús. 
Disponível em: 
< https://www.youtube.com/watch?v=bnU_GFhIjic>. Acesso em: 27 abr. 2023. 
 
5.3. Autômato finito determinístico 
Um autômato finito determinístico AFD ou simplesmente autômato finito M é uma 5-
upla ordenada: 
 M = (∑, Q, 𝜹, q0, F) 
Na qual: 
 
∑ é um alfabeto de símbolos de entrada, ou simplesmente alfabeto de entrada; 
Q é um conjunto de estados possíveis do autômato o qual é finito; 
δ é uma função programa ou simplesmente programa, ou ainda função de transição: 
 
𝜹: 𝑸 ∗ ∑ ⟶ 𝑸 
A qual é uma função parcial, supondo que a função programa é definida para um estado 
p e um símbolo a, resultando no estado q então: 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
 𝜹(𝐩, 𝐚) = 𝐪 
É uma transição do autômato: 
q0 é um elemento distinguido de Q sendo o estado inicial; 
F é um subconjunto de Q sendo o conjunto de estados finais. 
Um autômato finito pode ser representado na forma de um diagrama onde: 
• Estados são nodos, representados por círculos; 
• Transições são arestas para ligar os nodos correspondentes. Por exemplo uma 
transição do tipo 𝜹(q, a) = p como demonstrado abaixo: 
 
Figura 1.2 – Diagrama AFD - transição 
 
 
Fonte: Paulo Blauth Menezes, 2011. 
 
• Estados iniciais e finais são representados de forma distinta dos demais, como 
demonstrado abaixo: 
 
Figura 1.3 – Diagrama AFD – estado inicial (esquerda) e final (direita) 
 
Fonte: Paulo Blauth Menezes, 2011. 
 
• Transições paralelas possuem os mesmos nodos de origem e destino, podem 
alternativamente ser representadas, por exemplo suponhamos 𝜹(q, a) = p e 𝜹(q, 
b) = p, como demonstrado abaixo: 
 
 
 
 
Teoria da Computação 
 
Núcleo de Educação a Distância| Faculdade Impacta 
Figura 1.4 – Diagrama AFD – representações alternativas para transições paralelas 
 
Fonte: Paulo Blauth Menezes, 2011. 
 
 
Outra forma de demonstrar uma função programa é utilizando uma tabela de dupla 
entrada, por exemplo para uma transição do tipo 𝜹(𝐩, 𝐚) = 𝐪 podemos utilizar a tabela 
como abaixo: 
 
 
 
Tabela 1.1 – Função programa AFD 
𝜹 a ... 
p q ... 
q ... ... 
Fonte: Paulo Blauth Menezes, 2011. 
 
Autômato finito aa ou bb como subpalavra 
Considere a seguinte linguagem sobre o alfabeto {a, b}: 
 L1 = {w | w possui aa ou bb como subpalavra} 
O autônomo finito: 
 M1 = ({a,b}, {q0, q1, q2, qf}, 𝜹1, q0, {qf}) 
Onde 𝜹1 é dada conforme tabela 1.2, reconhece a linguagem L1, o autômato M1 é 
representado pelo diagrama da figura 1.5. O algoritmo apresentado usa os estados q1 e q2 
para memorizar o símbolo anterior lido, assim: 
• q1 representa o símbolo anterior é a; 
• q2 representa o símbolo anterior é b; 
• qual a informação memorizada por q0 e qf? 
 
Tabela 1.2 – Função programa AFD – sequência de dois símbolos iguais 
 
𝜹1 a b 
q0 q1 q2 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
q1 qf q2 
q2 q1 qf 
qf qf qf 
Fonte: Paulo Blauth Menezes, 2011. 
Após identificar dois a ou dois b consecutivos o autômato assume o estado qf estado final, 
e varre o sufixo da palavra de entrada, somente para terminar o processamento. 
 
Figura 1.5 – Diagrama AFD – sequência de dois símbolos iguais 
 
Fonte: Paulo Blauth Menezes, 2011. 
 
Para ilustrar a computação do autômato finito M1 para a entrada w = abba que é aceita: 
 
Figura 1.6 – Computação AFD – sequência de dois símbolos iguais 
 
Fonte: Paulo Blauth Menezes, 2011. 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
 
Autômato finito sempre para 
Em um autômato finito sempre para ao analisar qualquer entrada como, ou qualquer 
palavra finita, um símbolo da entrada é lido a cada aplicação da função programa, não 
existe a possibilidade de ciclo loop (laço) infinito. 
A parada do processamento de um autômato finito para uma entrada w pode ser de duas 
maneiras: 
• Aceita a entrada w – após processar o último símbolo da fita o autômato assume 
um estado final; 
• Rejeita a entrada w – neste caso teremos duas possibilidades: 
 Após processar o último símbolo da fita o autômato assume um estado não final; 
 Em algum momento, durante o processamento de w, a função programa é 
indefinida para o argumento, isto é para o estado corrente e símbolo lido da fita. 
 
Autômato finito x grafo finito direto 
Qualquer autômato finito pode ser visto como um grafo finito direto, sendo grafo finito 
direto aquele em que nodos e arcos são finitos e arcos são direcionados, nas seguintes 
situações: 
• Podem existir arcos paralelos, onde os arcos possuem os mesmos nodos de origem 
e destino; 
• Dois ou mais arcos podem ser identificados com os mesmos símbolos do alfabeto; 
• Existe um nodo distinto denominado estado inicial; 
• Existe um conjunto de nodos distintos cujos os elementos são denominados de 
estados finais. 
Existem muitas definições alternativas de autômato finito usam a definição de grafo como 
base, é comum considerar um autômato finito como um grafo finito direto especial. 
Utilizando esta interpretação conseguimos correlacionar a teoria dos autômatos com a 
teoria dos grafos herdando desta forma vários resultados da teoria dos grafos. 
Para definirmos formalmente o comportamento de um autômato finito é necessário 
estender a função programa, usando como argumento um estado e uma palavra o que 
permitirá determinar as computações possíveis. 
 
Função programa estendida, computação 
Seja M = (∑, Q, 𝜹, q0, F) um autômato finito determinístico, a função programa estendida 
ou computação de M, denotada por: 
 𝜹*: Q x ∑*⟶Q 
A função programa 𝜹: Q x ∑ ⟶Q estendida para palavras pode ser definida como: 
 𝜹*(q, 𝜺) = q 
 𝜹*(q, aw) = 𝜹*( 𝜹(q, a), w) 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Portanto a função programa estendida consiste na sucessiva aplicação da função programa 
para cada símbolo da palavra, com base em um dado estado. Contudo podemos observar 
se a entrada for vazia o autômato ficará parado no estado corrente. 
Par verificar se um autômato finito aceita ou rejeita uma entrada w aplica-se a função 
programa estendida para a entrada w a partir do estado inicial do autômato. 
 
Função programa estendida 
Considere o autômato finito M1 = ({a, b}, {q0, q1, q2, qf}, 𝜹1, q0, {qf}) levando em 
consideração o autômato finito aa ou bb como subpalavra, a computação da palavra abaa 
a partir do estado inicial q0 seria: 
𝜹*(q0, abaa) = função estendida sobre abaa 
𝜹*( 𝜹(q0, a), baa) = processa abaa 
𝜹*(q1, baa) = função estendida sobre baa 
𝜹*( 𝜹(q1, b), aa) = processa baa 
𝜹*(q2, aa) = função estendida sobre aa 
𝜹*( 𝜹(q2, a), a) = processa aa 
𝜹*(q1, a) = função estendida sobre a 
𝜹*( 𝜹(q1, a), 𝜺) = processa a 
𝜹*(qf, 𝜺) = qf = função estendida sobre 𝜺: fim da indução 
Portanto a palavra é aceita. 
A função programa estendida permite definir a linguagem aceita bem como a linguagem 
rejeitada por um autômato finito. 
 
Linguagem aceita, linguagem rejeitada 
Seja M = (∑, Q, 𝜹, q0, F) um autômato finito determinístico, a linguagem aceita ou 
linguagem reconhecida por M, representada por: 
 ACEITA(M) ou L(M) 
Considerando que se trata de um conjunto de todas as palavras pertencentes a ∑* aceitas 
por M, desde o estado inicial q0, ou seja: 
 L(M) = ACEITA(M) = {w | 𝜹*(q0, w) ∈ F} 
Já a linguagem rejeitada por M é representada por: 
 REJEITA(M) 
Considerando que se trata de um conjunto de todas as palavras pertencentes a ∑* 
rejeitadas por M, desde o estado inicial q0, ou seja: 
 REJEITA(M) = {w | 𝜹*(q0, w) ∉ F ou 𝜹*(q0, w) é indefinida} 
Sendo ∑* o conjunto universo, as seguintes afirmações são verdadeiras: 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
ACEITA(M) ∩ REJEITA(M) = ∅ 
ACEITA(M) ∪ REJEITA(M) = ∑* 
~ACEITA(M) = REJEITA(M) 
~REJEITA(M) = ACEITA(M) 
Cada autômato finito M definido sobre o alfabeto ∑ induz uma partição do conjunto de 
todas as palavras ∑* em duas classes de equivalência: ACEITA(M) e REJEITA(M), 
conforme demonstrado abaixo: 
 
Tabela 1.3 – Partição de ∑* induzida por autômato finito M 
 
ACEITA(M) REJEITA(M) 
Fonte: Paulo Blauth Menezes, 2011. 
 
Diferentes autômatos finitos podem aceitar uma mesma linguagem. Nesta situação 
utilizamos a próxima definição. 
 
Autômatos finitos equivalentes 
Dois autômatos finitos M1 e M2 são ditos autômatos finitos equivalentes se e somente se: 
 ACEITA(M1) = ACEITA(M2) 
 
Linguagem regular, linguagem tipo 3 
Uma linguagem L é dita uma linguagem regular ou linguagem tipo 3 se existe pelo menos 
um autômato finito determinístico que aceita L. 
Para a linguagem L1, por exemplo o autômato finito: aa ou bb como subpalavra, é regular. 
Quando falamos do autômato finito: vazia, todas as palavras, considerando as seguintes 
linguagens sobre o alfabeto {a, b}: 
 L2 = ∅ e L3 = ∑* 
Os autômatos finitos: 
M2 = ({a, b}, {q0}, 𝜹2, q0, { }) e M3 = ({a, b}, {q0}, 𝜹3, q0, {q0}) 
Como demonstrado na figura abaixo: 
 
∑* 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Figura 1.7 – Diagrama AFD – vazia à esquerda e todas as palavras à direita 
 
Fonte: Paulo Blauth Menezes, 2011. 
 
Sendo para os quais 𝜹2 e 𝜹3 são dados segundo as tabelas abaixo: 
 
Tabela 1.4 – Função programa AFD – vazia à esquerda e todas as palavras à direita 
 
𝜹2 a b 
q0 q0 q0 
Fonte: Paulo Blauth Menezes, 2011. 
 
Para o autômato finito: número par de cada símbolo, vamos considerar a seguinte 
linguagem sobre o alfabeto {a, b}: 
 L4 = {w | w possui um número par de a e um número par de b}O autômato finito: 
 M4 = ({a, b}, {q0, q1, q2, q3}, 𝜹4, q0, {q0}) 
 
Figura 1.8 – Diagrama AFD – número par de cada símbolo 
 
Fonte: Paulo Blauth Menezes, 2011. 
Tal que ACEITA(M4) = L4, portanto L4 é uma linguagem regular. 
 
𝜹3 a b 
q0 q0 q0 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Função programa x função programa estendida 
Uma função programa 𝜹 e sua correspondente extensão 𝜹* podem ser ambas 
representadas por 𝜹, esta simplificação de notação é adotada para todas as funções 
estendidas. 
Computações x caminhos de um grafo 
Ao relacionarmos a teoria dos autômatos com a teoria dos grafos, encontra-se uma forte 
relação entre as computações de um autômato finito e os caminhos do correspondente 
grafo finito direto. Efetivamente dado um autômato o desenvolvimento do 
correspondente grafo com todos os caminhos, incluindo os de tamanho zero, é tal que: 
• O conjunto de todos os caminhos corresponde as computações possíveis do 
autômato finito; 
• O subconjunto de todos os caminhos com origem no estado inicial e destino em 
algum estado final corresponde à linguagem aceita; 
• O subconjunto de todos os caminhos com origem no estado original e destino em 
algum estado não final corresponde à linguagem rejeitada. 
 
Figura 1.9 – Função programa estendida x caminhos de um grafo 
 
Fonte: Paulo Blauth Menezes, 2011. 
Com base na figura acima, pode concluir: 
a) O autômato finito M definido sobre o alfabeto {a, b, c, d} é ilustrado à esquerda; 
b) O autômato M, desenvolvido com seus caminhos, suas computações, é ilustrado 
no centro onde podemos observar que: 
• Em cada estado a inclusão de um endotransição, a transição com o mesmo 
nodo origem e destino, etiquetado por 𝜺 corresponde ficar parado no 
mesmo estado quando a entrada for vazia, um caminho de tamanho zero. 
Tais endotransições são interpretadas como faz nada, no inglês usamos o 
termo no operation – nop, uma instrução existente nos sistemas 
computadores reais; 
• Cada caminho incluído é etiquetado, conectando-se as etiquetas dos 
caminhos componentes, sendo que a palavra vazia 𝜺 é elemento neutro da 
concatenação, podemos observar que se o autômato original possuir algum 
ciclo, existirão infinitos caminhos contudo todos serão etiquetados por 
palavras, cadeias de símbolos de tamanho infinito; 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
c) À direta são representados: 
• O conjunto de todas as computações possíveis; 
• A linguagem aceita, subconjuntos de caminhos com origem no estado 
inicial e destino em algum estado final. 
 
Você sabia? 
Vamos aprofundar o conhecimento sobre Autômatos Finitos Determinísticos? Assista 
ao vídeo Autômatos finitos determinísticos - Definições – Canal Carla quem disse. 
Disponível em: 
< https://www.youtube.com/watch?v=0W_HK4MYKL8>. Acesso em: 27 abr. 2023. 
 
 
 
Considerações finais 
 Como vimos podemos definir a teoria dos autômatos como o estudo das máquinas 
abstratas também chamadas de autômatos, sendo de grande auxílio na resolução de 
problemas computacionais por facilitar tais resoluções com a utilização dos autômatos. 
O autômato executa quando receber sequências de dados de entrada em intervalos de 
tempo discretos. Quando uma nova entrada é recebida, ela faz a transição para outro 
estado com base em uma função que recebe o estado atual e o código como 
parâmetros. Essa função é chamada de função de transmutação. Contém um subconjunto 
de estados de autômato que é definido como um conjunto de estados de aceitação. Se o 
status final aceitar, o autômato aceitou essa palavra. Ocorrência contrário, a palavra será 
rejeitada. O conjunto de todas as palavras aceitas pelo autômato é chamado de linguagem 
reconhecida pelo autômato. Um subconjunto da linguagem do autômato é a linguagem 
que o autômato reconhece. 
 
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.