Linguagens Formais e Autômatos - Leandro Dionízio - Aula 03 AFND

Prévia do material em texto

Linguagens Formais
Leandro Dionízio Ramos
1
Autômato finito determinístico
• Para cada entrada (símbolo) existe um e 
somente um estado ao qual o autômato pode 
transitar a partir de seu estado atual e do 
símbolo lido.
2
Autômato finito não determinístico
• Autômato finito não-determinístico pode estar 
em vários estados ao mesmo tempo;
3
Autômato finito não determinístico
• Um autômato finito não determinístico aceita uma 
cadeia de entrada quando houver alguma sequência 
de movimentos que o leve da configuração inicial 
para uma configuração final.
4
Autômato finito não determinístico
• Diferentemente do autômato finito determinístico, 
em que essa sequência, se existir, é única para cada 
cadeia de entrada, no caso do autômato finito não 
determinístico é possível que exista mais de uma 
sequência que satisfaça a essa condição para uma 
dada cadeia de entrada.
5
Autômato finito não determinístico
• Sempre que o autômato finito não-determinístico se 
deparar com mais de uma possibilidade de 
movimentação, é feita a escolha (arbitrária) de uma das 
alternativas; em caso de insucesso no reconhecimento, 
deve-se considerar sucessivamente cada uma das demais 
alternativas ainda não consideradas, até o seu 
esgotamento; persistindo o insucesso, e esgotadas as 
alternativas, diz-se que o autômato rejeita a cadeia.
6
Autômato finito não determinístico
• AFD vs. AFND
• Determinístico
– Transições bem-definidas
– Função de transição leva a um único estado
– Sequência de estados é única para cada palavra
• Não determinístico
– Transições ambíguas
– Função de transição leva a vários estados alternativos
– Várias sequências possíveis
7
Autômato finito não determinístico
• Até agora, quando um AF está em um dado estado e lê o 
próximo símbolo da entrada, nós sabemos exatamente qual 
seu próximo estado (é bem determinado)
• Máquinas que se comportam dessa forma são chamadas de 
determinísticas.
• Máquinas não-determinísticas são aquelas em que diversas 
escolhas podem existir para o próximo estado em qualquer 
ponto da execução.
8
Autômato finito não determinístico
• O próximo estado não é necessariamente unicamente 
determinado pelo estado atual e pelo símbolo de entrada.
• Podemos ter zero, uma ou mais transições de estado com o 
mesmo símbolo de entrada.
9
Autômato finito não determinístico
• Exemplo: AFND M1
• Um estado pode ter zero, um ou mais arcos “saindo” para 
cada símbolo do alfabeto;
• Estado inicial q0
• Estado final q2
10
Autômato finito não determinístico
• Exemplo: AFND M1
• Vamos considerar M1 com a entrada 110
1111
q0
1
q0 q1
q0 q1
1
1 1
Paralisado
q2
0
q0
0
Aceitação!
Autômato finito não determinístico
• Exemplo: AFND M1
• Vamos considerar M1 com a entrada 110
• Estado de Aceitação!
12
q0
1
q0 q1
q0 q1
1
1 1
Paralisado
q2
0
q0
0
Aceitação!
Autômato finito não determinístico
• Exemplo: AFND M1
• M1 com a entrada 110. Estado de Aceitação!
13
q0
1
q0 q1
q0 q1
1
1 1
Paralisado
q2
0
q0
0
Aceitação!
Autômato finito não determinístico
• Definição formal:
Quíntupla M = (Σ, Q, δ , q0, F):
– Σ: alfabeto de símbolos de entrada
– Q: conjunto finito de estados possíveis para M
– δ (beta): função transição ou função programa 
definida em Q x Σ = Q
– q0: estado inicial de M, sendo (q0 ∈ Q)
– F: conjunto de estados finais, tal que (F ∈ Q)
Autômato finito não determinístico
• Outro exemplo:
Autômato finito não determinístico
• Teste a L = {01001}:
Autômato finito não determinístico
• Exemplos: L = {01001}
Autômato finito não determinístico
• Exemplo de AFND
• Reconhece a linguagem ab*c*
18
Autômato finito não determinístico
19
Autômato finito não determinístico
• Duvidas???
20