Aula 6- AFND

TEORIA DA COMPUTAÇÃO
Aula 6
Autômatos Finitos
Não Determinísticos
Docente:
Golda Kangunga
04/11/2024
Sumário:
• Linguagens Regulares
• Autômatos Finitos Não Determnísticos
Linguagens Regulares
Uma linguagem L é dita uma Linguagem Regular se existe pelo menos um AF que
aceita L. Então, temos que L(M4)=∅ e L(M5)=∑ ∗ 𝑠ã𝑜 𝐿𝑖𝑛𝑔𝑢𝑎𝑔𝑒𝑛𝑠 𝑅𝑒𝑔𝑢𝑙𝑎𝑟𝑒𝑠
q0 A,b L(M4)=∅
q0 A,b
L(M5)=∑∗
• Diferentes autómatos fiitos podem aceitar uma mesma
mensagem.
• M1 e M2 são Autômatos Finitos Equivalentes se e somente se:
L(M1)=L(M2)
Na teoria da ciência da computação e teoria formal de
linguagem, uma linguagem regular é uma linguagem
formal que pode ser expressa usando expressões
regulares, ou seja, uma linguagem produzida utilizando as
operações de concatenação, união e fecho de Kleene sobre
os elementos de um alfabeto. De acordo com a hierarquia
de Chomsky, linguagens regulares são aquelas geradas por
gramática regulares.
As linguagens regulares são utilizadas para descrever
dispositivos que realizam computações simples, como os
autômatos finitos, pois representam a linguagem mais
elementar classificada pela hierarquia de Chomsky que não
requer muita memória para ser reconhecida.
A colecção de linguagens regulares sobre um alfabeto Σ qualquer é
definida recursivamente seguindo as regras abaixo:
• A linguagem vazia (L = Ø) é uma linguagem regular.
• Se x é um elemento qualquer do alfabeto Σ, a linguagem formado pelo
conjunto desse elemento (L = {x}) é uma linguagem regular.
• Se A e B são linguagens regulares, então as linguagens formadas pela
união (L = A ∪ B), concatenação (L = A • B) e fecho de Kleene (L = A* ou L
= B*) desses conjuntos também são linguagens regulares.
• Nenhuma outra linguagem sobre o alfabeto Σ é regular.
Todas as linguagens finitas são regulares, em particular a
linguagem composta unicamente pela cadeia vazia (L = {ε}
= Ø*) é regular.
Considerando o alfabeto Σ = {a, b}, é possível descrever
linguagens regulares como "todas cadeias que contenham
um número par de 'a' ou "todas cadeias formadas por uma
quantidade qualquer de 'a' seguido de uma quantidade
qualquer de 'b'" e assim por diante.
Não podemos considerar uma linguagem regular aquelas
linguagens que requerem a actuação de uma memória para
estruturar os elementos de suas cadeias, isto é, quando a
frequência de um elemento da cadeia determina a
frequência de outro elemento da mesma cadeia. Portanto,
linguagens como "todas cadeias de 'a' seguido de 'b', onde
o número de 'a' é igual ao de 'b'", não são regulares pois o
número de 'a' determina o número de 'b'.
Uma linguagem regular satisfaz as seguintes
propriedades que são equivalentes:
• ela é a linguagem descrita por uma expressão regular.
• ela pode ser aceita por um autômato finito
determinístico.
• ela pode ser aceita por um autômato finito não
determinístico.
• ela pode ser aceita por um autômato finito alternado.
• ela pode ser gerada por uma gramática regular.
• ela pode ser gerada por uma gramática de prefixos.
• ela pode ser aceita por uma Máquina de Turing que apenas
faz leituras.
• ela pode ser definida em um monádico da lógica de segunda
ordem.
• ela é reconhecida por algum Monoide finito.
Hierarquia de Chomsky
Tipos de linguagens:
Autômatos Finitos Não-Determinísticos
Um AF é aquele que permite zero, uma ou mais transições de
um estado p, com o mesmo símbolo a ∈ ∑.
𝛿 𝑝, 𝑎 = (𝑞1, 𝑞2, … 𝑞𝑟)
Quando uma máquina está num dado estado e lê o próximo
símbolo de entrada, sabemos que estado será o próximo.
Chamamos isso de computação determinística. Em uma máquina
não determinística, várias escolhas podem existir para cada
próximo estado em qualquer ponto.
Se um estado com um símbolo 𝜀 sobre uma seta é encontrado,

sem ler uma entrada, a máquina divide-se em múltiplas cópias,
uma seguindo cada uma das setas saindo rotuladas com 𝜀 e uma
permanecendo no estado corrente
Varias escolhas podem existir para o próximo estado em
qualquer ponto.
Função de transição (mapeamento)-𝛿 𝑝, 𝑎 = (𝑞1, 𝑞2, … 𝑞𝑟)
Exemplo: AFN
W=00101
𝛿 𝑞0, 0 = {𝑞0, 𝑞1}
Linguagem aceita por N1: L={w|w∈ {0,1}∗ e w termina com

01}
Autômatos finitos não determinísticos
Uma cadeia w= w1w2…wn é aceita por um autómato finito não
determinístico (AFN) se existir pelo menos uma sequência de
transições que leva 𝛿 ∗ (q0,w) a um estado de aceitação ao
processar w.
Pode-se imaginar que a máquina se divide em múltiplas cópias
de si mesma e segue todas as possibilidades em paralelo.
Autômatos finitos não determinísticos (AFN) são uma
generalização de autómatos finitos determinísticos (AFDs):
• Todo Autômatos finitos determinísticos (AFD) é um Autômatos
finitos não determinísticos(AFN)
• Em um AFN podem existir vários caminhos para a aceitação de
w, enquanto que em um AFD, apenas um 𝛿 𝑞0, 𝑤 𝜖 𝐹
Exemplo-2:
Linguagem aceita por N8: W=00101

L={w|w ∈ {0,1}∗ e w possui um 1 em wn-2}
Uma outra maneira de ver a computação nesse Autômato
finitos não determinístico (AFN) é que ele permanece em q2 até
que se “adivinhe” que está no final de w(palavra). Nesse ponto,
ele ramifica para o estado q1 e segue para q2 e q3.
AFNs podem ser mais simples de planejar, além de ocupar
mais espaços, entender e funcionamento desse AFD é muito
mais complicado.
Um autómato finito não determinístico (AFN) é uma 5-upla (Q, ∑,
𝛿, 𝑞0, 𝐹), em que:
• Q é um conjunto finito de estados;
• ∑ é o alfabeto de cadeia de entrada;
• 𝛿: 𝑄 𝑥 ∑ -> 2𝑄 é a função de transição que mapeia Q x ∑ em
2𝑄 .
- 𝛿(p,a)=(q1, q2,…,qr)
• Q0 ∈ Q é o estado inicial
• F ⊆ Q é o conjunto de estados de aceitação.
AFN-Função de transição
𝛿(p,a)=(q1, q2,…,qr)
então quando o AFN está no estado p e lê o símbolo ‘a’, os
próximos estados serão (q1, q2,…,qr)
a b
->q0 (q0, q1) {q0}
q1 ∅ {q2}
*q2 ∅ ∅
Função de transição estendida
A função de transição estendida (ou programa) de N, denotada por
𝛿 ∗ : Q x ∑ -> 2𝑄
É a função 𝛿 ∗ : Q x ∑ -> 2𝑄 estendida para palavras definida como
𝛿 ∗ (q,𝜀) = {q}
𝛿 ∗ (q,𝑤𝑎) = {p| para algum r ∈ 𝛿 ∗ (q,𝑤), p está em 𝛿 (r,a)}
Ou seja, é a sucessiva aplicação da função de transição para cada
símbolo de w.
Funcionamento de um AFN
Condições de parada após processar o último símbolo.
•Aceita a entrada: se existir pelo menos um caminho, partindo
de q0 que leve N até um estado de aceitação;
•Rejeita a entrada: se não existir nenhum caminho partindo
de q0, que leve N até um estado de aceitação;
Linguagem reconhecida
A linguagem reconhecida pelo AFN N= (Q, ∑, 𝛿, 𝑞0, 𝐹)
L(N)= {w|w ∈ ∑∗ e 𝛿 ∗ q0, w ∩ 𝐹 ≠ ∅}
De forma análoga, w é aceita por M se 𝛿 ∗ q0, w ∩ 𝐹 ≠ ∅
Exemplo-AFN
Considere N8 e a cadeia de entrada w=01001
Equivalência entre AFD e AFN
A classe de linguagens aceitas pelos AFNs é a mesma aceita
pelos Autômatos Finitos Determinísticos (AFDs). O não
determinismo não adiciona poder computacional aos autómatos
finitos.
Vantagens dos AFNs
• Podem ser mais fáceis de projectar;
• Em geral, são mais sucintos (menor espaço);
Qualquer linguagem reconhecida por um autômatos finitos não
determinísticos (AFN) N também pode ser reconhecida por um
autômatos finitos determinísticos (AFD) M equivalente:
L(N) = L(M)
Equivalência:
AFD -> AFN: Não precisa ser provado, basta 𝛿 D(q,a)= p-> 𝛿 N (q, a)={p}
AFN->AFD: prova por construção
Vamos definir o AFD equivalente M=(QD, ∑, 𝛿 D, 𝑞, 𝐹 ), tal que:
• QD = 2𝑄 , todos os subconjuntos de Q;
• -qij…k ∈ QD representa o conjunto {qi, qj,…, qk}
• q’0 = q0 é o estado inicial;
• FD é o conjunto de estados que contém um estado final do AFN
N
Muitos estados no AFD equivalente não são acessíveos a partir
de q0: devemos inserir apenas estados acessíveis partindo de q0
criando apenas estados alcançáveis.
Próxima Aula
• Exercícios: AFD e AFN
• Autômatos Finitos com Movimentos Vazios (AFNe)
• Definição formal de um AFNe
Exercícios
1. Defina um autômato finito determinístico (AFD) que reconheça
a linguagem composta por todas as cadeias que contêm um
número par de 0s.
2. Desenhe o diagrama de estados de um autômato que aceita a
linguagem de cadeias que terminam com a letra "a".
3. Construa a tabela de transição para um autômato que aceita
cadeias formadas apenas por 0s e 1s, que contenham pelo
menos um 1.
Exercícios
Dado o autômato A definido pelas seguintes transições:
• Estado Inicial: q0q0q0
• Estado de Aceitação: q1q1q1
Estado q0: 0 → q0, 1 → q1
Estado q1: 0 → q2, 1 → q1
Estado q2: 0 → q2, 1 → q2
Testar as cadeias: "010", "111", "100".
Exercícios
1. Minimização de Autômato-> Problema: Dado um autômato com os
estados {q0, q1, q2} e as transições:
• q0 —0→ q1
• q0 —1→ q0
• q1 —0→ q1
• q1 —1→ q2
• q2 —0→ q1
• q2 —1→ q0
Referências Bibliograficas
• Diverio, T. A., & Menezes, P. B. (1999). Teoria da Computação-

Máquinas Universais e computabilidade. Porto Alegre.
• Sipser, M. (2005). Uma Introdução a Teória da Computação.

PWS Publishing Company c 1997.

Aula 6- AFND

Enviado por

Direitos autorais:

Formatos disponíveis

Aula 6- AFND

Enviado por

Dados do documento

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Aula 6- AFND

Enviado por

Direitos autorais:

Formatos disponíveis

TEORIA DA COMPUTAÇÃO

Se um estado com um símbolo 𝜀 sobre uma seta é encontrado,

𝛿 𝑞0, 0 = {𝑞0, 𝑞1}

Linguagem aceita por N1: L={w|w∈ {0,1}∗ e w termina com

Linguagem aceita por N8: W=00101

• Diverio, T. A., & Menezes, P. B. (1999). Teoria da Computação-

• Sipser, M. (2005). Uma Introdução a Teória da Computação.

Você também pode gostar