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