Linguagens Formais e Aut matos Aula 7 Aut matos com Sa da 14.11.2017.2

Prévia do material em texto

Professor
Me. Paulo David
pd.mnpa@gmail.com
Faculdade Maurício de Nassau
Curso: Sistemas de Informação 
Disciplina: Linguagens Formais e Autômatos
Professor: Me. Paulo Roberto Sousa David
Autômatos com Saída
• O conceito básico de Autômato Finito possui
aplicações práticas restritas, pois a informação
de saída é limitada a lógica binária aceita/rejeita.
• Sem alterar a classe de linguagens reconhecidas,
é possível estender a definição de Autômato
Finito, incluindo-se a geração de uma palavra de
saída.
• As saída podem ser associadas:
✓ Às transições: Máquina de Mealy.
✓ Aos estados: Máquina de Moore.
• Tanto na máquina de Mealy quanto na máquina
de Moore, a saída não pode ser lida, ou seja,
não pode ser usada como memória auxiliar.
• A saída:
✓ é definida sobre um alfabeto especial,
denominado de alfabeto de símbolos de
saída, o qual pode ser igual ao alfabeto de
entrada.
✓ é armazenada em uma fita de saída
independente da de entrada.
• A saída:
✓ a cabeça da fita de saída move uma célula
para a direita a cada símbolo gravado.
✓ o resultado do processamento do autômato
finito é o seu estado final (condição de
aceita/rejeita) e a informação contida na
saída.
• É um Autômato Finito modificado de forma a
gerar uma palavra de saída (a qual pode ser
vazia) para cada transição.
Definição:
• UmaMáquina de Mealy M é um Autômato Finito
Determinístico com saídas associadas as
transições.
• É representado por uma 6-upla:
M = (, Q, , q0, F, )
Portanto:
• Σ - alfabeto (de símbolos) de entrada
• Q - conjunto de estados (finito)
• δ - função programa ou função de transição
(função parcial) - δ: Q×Σ→Q×Δ*
• q0 - elemento distinguido deQ: estado inicial
• F - subconjunto deQ: conjunto de estados finais
• Δ - alfabeto (de símbolos) de saída
Portanto:
• , Q, q0, F são como em Autômato Finito
Determínistico.
•  é a função programa, que pode ser
representada como um diagrama como em AF,
adicionando, na etiqueta de cada transição, a
saída associada, quando diferente da palavra
vazia.
•  é um alfabeto de símbolos de saída, ou
simplesmente alfabeto de saída.
• Possui uma segunda função, que gera uma
palavra de saída (que pode ser vazia) para cada
estado da máquina.
Definição
• Uma Máquina de Moore M é um Autômato
Finito Determinístico com saídas associadas
aos Estados.
• É representado por uma 7-upla:
M = (Σ, Q, δ, q0, F, Δ, δS)
Portanto:
• Σ - alfabeto (de símbolos) de entrada
• Q - conjunto de estados (finito)
• δ - função programa ou função de transição
(função parcial) - δ: Q×Σ→Q
• q0 - elemento distinguido deQ: estado inicial
• F - subconjunto deQ: conjunto de estados finais
• Δ - alfabeto (de símbolos) de saída
• δS - função de saída (função total) - δS: Q→Δ*
Portanto:
• , Q, q0, , F são como em Autômato Finito
Determínistico.
•  é como na máquina de Mealy, um alfabeto de
símbolos de saída, ou simplesmente alfabeto de
saída.
•  é a função programa, que pode ser
representada como um diagrama como em AF,
adicionando, na etiqueta de cada estado, a
saída associada, quando diferente da palavra
vazia.
Exemplos:
Máquina de Moore
Máquina de Mealy
Exemplo: Aplicação emHipertexto e Hipermídia.
Hipertexto com objetivo de disponibilizar um Curso
sobre Autômatos com Saída na www, usando
Máquina deMoore.
Alfabeto de entrada: {próxima, exercício, anterior,
resumos, saída}
Alfabeto de saída: {A, B, C, D, E, F, G, H, I, J, K, L, M}
Exemplo: Aplicação emHipertexto e Hipermídia.
A - IntroduçãoAF B - DefiniçãoAFD
C - ExemploAFD D - ExercícioAFD
E - IntroduçãoAF comSaída
F - DefiniçãoMáquina deMealy
G - Exemplo Máquina deMealy
H - Exercício Máquina deMealy
I - DefiniçãoMáquina deMoore
J - ExemploMáquina deMoore
K - Exercício Máquina deMoore
L - Conclusões M - Fim
Exemplo: Aplicação emHipertexto e Hipermídia.
Professor
Me. Paulo David
pd.mnpa@gmail.com
Faculdade Maurício de Nassau
Curso: Sistemas de Informação 
Disciplina: Linguagens Formais e Autômatos
Professor: Me. Paulo Roberto Sousa David
Autômatos com Saída