Baixe o app para aproveitar ainda mais
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ε
Compartilhar