Aula 4 Autômatos Finitos Não Determinísticos

Prévia do material em texto

Linguagens Formais e 
Autômatos 
 
Autômatos Finitos não 
Determinísticos 
 Prof. Paulo
pfanio@gmail.com
Henrique
Adaptação do Material da Profª Débora Souza
Introdução a autômato finito não 
determinístico (AFN) 
• Em uma computação por AFD (autômato finito 
determinístico) temos: 
• Máquina esta em um estado → lê o próximo símbolo de 
entrada → passa para o próximo estado. 
 
• Está determinado! 
• Computação determinística 
Fig. 1: Exemplo simples de AFD, sem marcação 
de estado inicial ou estado(s) de aceitação 
Uma máquina pode estar em dois ou 
mais estados ao mesmo tempo? 
Introdução a autômato finito não 
determinístico (AFN) 
Estado anterior 
Símbolo lido 
Conjunto de novos estados 
Fig. 2: Exemplo simples de AFN, sem marcação 
de estado inicial ou estado(s) de aceitação 
Autômato finito não 
determinístico 
• Ex. 1 – AFN (diagrama de estados): 
 
 
 
 
 
• Um autômato pode estar em vários estados ao mesmo 
tempo. 
 
• Dado a entrada 110, como seria o funcionamento deste 
autômato? 
Fig. 3: Exemplo de AFN 
Autômato finito não 
determinístico 
Fig. 4: Representação em árvore do funcionamento 
do exemplo 1 para entrada 110 
Autômato finito não 
determinístico 
• O não determinismo pode ser visto como uma 
espécie de computação paralela. 
• Processos podem estar rodando concorrentemente. 
 
• Um AFN se divide para acompanhar diversas 
escolhas. 
• Se ao menos um dos caminhos chegar ao estado de 
aceitação e a cadeia de entrada foi toda lida então, a 
computação inteira é aceita! 
Autômato finito não 
determinístico 
• Nem sempre é necessário calcular todos os 
caminhos possíveis no AFN para uma determinada 
cadeia. 
• Basta que se encontre um caminho que chegue ao 
estado de aceitação. 
Fig. 5: caminho de aceitação 
do exemplo 1 para entrada 110 
Autômato finito não 
determinístico 
• Ex. 2: 
Fig. 6: Exemplo de AFN 
Autômato finito não 
determinístico 
• Qual a computação que o autômato da Figura 6 faz 
para a cadeia de entrada aacd? Essa entrada é 
aceita? 
 
• Quais cadeias são reconhecidas pelo autômato da 
Figura 6? 
 
• Que operação está presente na construção desse 
autômato? 
Definição formal de um autômato 
finito não determinístico 
• Podemos definir matematicamente um autômato 
finito não determinístico D por meio uma quíntupla 
(ou uma 5-upla): 
 
D = (Q, ∑, δ, 𝑞0, F) 
 
• Onde: 
• Q é um conjunto finito conhecido como estados 
• ∑ é o alfabeto de símbolos de entrada 
• δ é a função de transição. É do tipo: Q x ∑ → 2Q 
• 𝒒𝟎 é o estado inicial (𝑞0 ∈ Q) 
• F é o conjunto de estados de aceitação (F ⊆ Q) 
 
Definição formal de um autômato 
finito não determinístico 
• Exceto pela função de transição, os demais 
componentes da definição formal de um AFN são 
exatamente os mesmos aplicados para um AFD. 
Definição formal de um autômato 
finito não determinístico 
• Ex. 3: 
 
 
 
 
• Podemos descrever M1 formalmente escrevendo M1 = 
(Q, ∑, δ, 𝑞1, F), onde: 
• Q = {q1, q2, q3, q4} 
• ∑ = {0, 1} 
• 𝑞1 é o estado inicial 
• F = {q4} 
Fig. 7: Exemplo de AFN 
Definição formal de um autômato 
finito não determinístico 
• δ é descrita como: 
 
 
 
 
 
 
• Ou pode ser descrita 
como: 
• δ(q1, 0) = q1 
• δ(q1, 1) = {q1, q2} 
• δ(q2, 0) = q3 
• δ(q2, 1) = q3 
• δ(q3, 0) = q4 
• δ(q3, 1) = q4 
• δ(q4, 0) = Ø 
• δ(q4, 1) = Ø 
 
0 1 
q1 {q1} {q1,q2} 
q2 {q3} {q3} 
q3 {q4} {q4} 
q4 - - 
Definição formal de um autômato 
finito não determinístico 
• Qual a definição formal do autômato apresentados 
no exemplo 2? 
Autômato do exemplo 2 (Fig. 6) 
Definição formal de um autômato 
finito não determinístico 
• ({q1, q2, q3, q4, q5, q6, q7, q8, q9, q10, q11}, {a, b, c, d}, δ, q1, {q4, q7, 
q11}), onde δ: 
 
a b c D 
q1 {q1, q2, q5, q8} {q1} {q1} {q1} 
q2 - {q3} - - 
q3 - - {q4} - 
q4 - - - - 
q5 - {q6} - - 
q6 - - - {q7} 
q7 - - - - 
q8 {q9} - - - 
q9 - - {q10} - 
q10 - - - {q11} 
q11 - - - 
AFN é mais poderoso que AFD? 
Relação entre AFD e AFN 
• Não necessariamente a facilidade do não 
determinismo aumenta o poder de 
reconhecimento de linguagens. 
 
• Qualquer AFN pode ser simulado por um AFD. 
• Realizam o mesmo processamento, ou seja, reconhecem 
a mesma linguagem. 
 
 
Conversão de AFD para AFN 
• Na forma gráfica, não seria necessário fazer 
alterações no AFD para convertê-lo para um AFN. 
 
• Uma pequena mudança ocorreria apenas na 
representação formal da função de transição: 
• Seria necessário transformar cada célula da tabela do 
AFD em um conjunto unitário contendo esse mesmo 
estado. 
Conversão de AFN para AFD 
• Ex. 4 – conversão de AFN em AFD: 
 
 
 
 
• N2 = ({q1, q2, q3}, {0, 1}, δ, q1, {q3}) onde δ: 
 0 1 
q1 {q1} {q1, q2} 
q2 {q3} - 
q3 - - 
Fig. 8: Exemplo de AFN 
Conversão de AFN para AFD 
• A grande pergunta é: como fazer os conjuntos de 
estados, presentes na tabela do AFN, aparecerem 
como um único estado no AFD? 
 
• Observações: 
• Usar um conjunto de estados do AFN como sendo um 
único estado para o AFD. 
• Por exemplo: {q1, q2} 
• Um estado com nome {q1, q2} representaria a situação 
em que o AFN estaria, ao mesmo, nesses dois estados. 
Conversão de AFN para AFD 
• Como converter: 
• O estado inicial será o mesmo do AFN. 
• Seu início nunca começa “bifurcado” em várias opções. 
• A partir do estado inicial, construímos as transições e 
“descobrimos” outros estados importantes para o novo 
autômato. 
 
 
 
• O conjunto {q1, q2} representa um novo estado e deverá 
ser representado por uma nova linha da tabela. 
 
0 1 
{q1} {q1} {q1, q2} 
Conversão de AFN para AFD 
• Como converter (cont.): 
 
 
 
 
• Observe que o estado {q1, q2} representa os estados q0 e q1 
ao mesmo tempo!! 
• A partir de q1, lendo 0 temos {q1}, e a partir de q2 acessamos 
{q3}. 
• Aqui precisamos utilizar a operação υ (união) para unir os 
resultados! 
• {q1} υ {q3} = {q1, q3} 
• O resultado da operação de união é inserido na célula da tabela. 
 
0 1 
{q1} {q1} {q1, q2} 
{q1, q2} 
Conversão de AFN para AFD 
• Estando em q1, lendo 1 temos {q1, q2}, e a partir de q2 
temos Ø. 
• {q1, q2} υ Ø = {q1, q2} 
 
 
 
 
 
• Agora basta apenas replicar estes passos até que todos os 
estados sejam “encontrados”. 
0 1 
{q1} {q1} {q1, q2} 
{q1, q2} {q1, q3} {q1, q2} 
0 1 
{q1} {q1} {q1, q2} 
{q1, q2} {q1, q3} {q1, q2} 
{q1, q3} {q1} {q1, q2} 
Conversão de AFN para AFD 
• Se não surgir um estado (conjunto), então a 
construção da tabela deve ser encerrada. 
 
• Quem são os estados de aceitação?? 
• Observe os estados de aceitação do AFN. 
• Se um AFN termina em um conjunto de estados, basta 
um deles ser estado de aceitação para aceitar uma 
cadeia. 
 
• Geralmente o estado inicial é marcado na tabela 
com uma → e o estado de aceitação com um *. 
Conversão de AFN para AFD 
 
 
 
• A partir da tabela pode-se construir a 
representação gráfica do autômato. 
0 1 
→{q1} {q1} {q1, q2} 
{q1, q2} {q1, q3} {q1, q2} 
*{q1, q3} {q1} {q1, q2} 
{q1, q2} 
{q1, q3} 
Fig. 9: Autômato convertido do exemplo 4 (Fig. 8) 
Conversão de AFN para AFD 
• Ex. 5: 
 
 
 
 
 
• N3 = ({q1, q2, q3}, {0, 1}, δ, q1, {q2}) onde δ: 
 
 
 
 
 
a b 
q1 {q2, q3} {q1, q3} 
q2 {q2} {q2} 
q3 {q2} - 
Fig. 10: Exemplo de AFN 
Conversão de AFN para AFD 
a b 
→{q1} {q2, q3} {q1, q3} 
*{q2, q3} {q2} {q2} 
{q1, q3} {q2,q3} {q1, q3} 
*{q2} {q2} {q2} 
Fig. 11: Autômato convertido do exemplo 5 (Fig. 10) 
{q1, q3} {q2, q3} 
Pode-se mudar de estado sem ler 
símbolo algum? 
Autômato finito com movimentos 
vazios 
• É conhecido por AFNε ou AFε. 
 
• Constituem uma generalização dos modelos de 
máquinas não determinística. 
 
• Um movimento vazio é uma transição sem leitura 
de símbolo algum da fita. 
• Exceto por uma eventual mudança de estados, nada 
pode ser observado sobre um movimento vazio. 
• Transições deste tipo usam como identificador a letra 
grega ε (épsilon). 
Autômato finito com movimentos 
vazios 
• A definição formal de um autômato com movimentos 
vazios é quase exatamente a mesma que de um AFN, a 
exceção fica por conta da função de transição. 
• δ: Q x (∑ ∪ {ε}) → 2Q 
 
• O processamento de um AFε é análogo ao de um AFN. 
 
• Adicionalmente, o processamento de uma transição 
para uma entrada vazia também é não determinística. 
Autômato finito com movimentos 
vazios 
• Ex. 6 – Autômato finito com movimentos vazios. 
 
 
 
 
 
• N4 = ({q1, q2}, {a, b}, δ, q1, {q2}) onde δ: 
 
Neste caso, a interrogação (?) 
representa o ε 
a b ? 
q1 {q1} - {q2} 
q2 - {q2} 
Fig. 12: Exemplo de AFε 
Autômato finito com movimentos 
vazios 
• Ex. 7: 
 
 
 
 
 
• N5 = ({q1, q2, q3}, {a, b}, δ, q1, {q1}) onde δ: 
Neste caso, a interrogação (?) 
representa o ε 
a b ? 
q1 - {q2} {q3} 
q2 {q3} {q3} - 
q3 {q1} - - 
Fig. 13: Exemplo de AFε