Baixe o app para aproveitar ainda mais
Prévia do material em texto
INE5317 Linguagens Formais e Compiladores Ricardo Azambuja Silveira INE-CTC-UFSC E-Mail: silveira@inf.ufsc.br URL: www.inf.ufsc.br/~silveira AULA 5: Autômatos Finitos 06/09/06 Ricardo Silveira 2 As Linguagens e os formalismos representacionais ● Os tipos de formalismos utilizados: – Denotacional: as linguagens são representadas por meio de uma função que caracteriza o conjunto de palavras admissíveis na linguagem ● EXPRESSÕES REGULARES – Axiomático: as linguagens são representadas através de regras que constituem uma Gramática que permite derivar todo o conjunto de sentenças ● GRAMÁTICAS – Operacional: as linguagens são representadas por máquinas abstratas ou autômatos, baseados em estados, em instruções primitivas e em como cada símbolo modifica cada estado ● AUTÔMATOS 06/09/06 Ricardo Silveira 3 Sistemas de Estados Finitos ● Um Sistema de Estados Finitos é um modelo matemático de sistemas com entradas e saídas discretas que pode assumir um número finito e pré-definido de estados ● Cada estado resume somente as informações do passado necessárias para determinar as ações para a próxima entrada 06/09/06 Ricardo Silveira 4 Tipos de autômatos ● Autômato finito ● Autômato com pilha ● Máquina de Turing com fita finita ● Máquina de Turing 06/09/06 Ricardo Silveira 518 LINGUAGENS REGULARES E AUTÔMATOS FINITOS ● Constituem um conjunto de linguagens decidíveis bastante simples e com propriedades bem definidas e compreendidas. ● Podem ser reconhecidas por Autômatos Finitos e são facilmente descritas por expressões simples, chamadas Expressões Regulares. ● Podem ser abordadas através de fomalismos: – Operacional ou reconhecedor: Autômato Finito (Determinístico e Não-determinístico e Vazio). – Axiomático ou gerador: Gramática Regular – Denotacional: Expressão Regular 06/09/06 Ricardo Silveira 620 Autômato Finito ● Um Autômato Finito é um reconhecedor de L.R. – Entende-se por reconhecedor de uma linguagem L um dispositivo que tomando uma seqüência w como entrada, responde “sim” se w ∈ L e “não” caso contrário. ● Os Autômatos Finitos classificam-se em: – Autômatos Finitos Determinísticos (AFD) – Autômatos Finitos Não-Determinísticos (AFND) – Autômatos Finitos com Movimentos Vazios (AFε) 06/09/06 Ricardo Silveira 7 Autômato Finito Determinístico ● Um autômato finito determinístico é uma máquina abstata composta por: – Fita ● Dispositivo de entrada que contém a informação a ser processada – Unidade de controle ● Reflete o estado corrente da máquina. Possui uma leitora que lê uma célula de cada vez e movimenta-se para a direita – Programa ou Função de Transição ● Comanda as leituras e define o estado da máquina 06/09/06 Ricardo Silveira 8 Autômato Finito Determinístico ● Um autômato finito determinístico (AFD)é uma 5- upla: – M= (Q, Σ, δ, q0,F) – Q é um conjunto de estados possíveis do autômato, o qual é finito; – Σ é um alfabeto de símbolos de entrada; – δ (delta) é um programa ou função de transição: δ:Q × Σ → Q – q0 é o estado inicial, tal que q0 é elemento de Q – F é o conjunto de estados a a b c c b a a Controle 06/09/06 Ricardo Silveira 9 Função de transição δ(q; a) = p para q, p ∈ K e a ∈ Σ, significando que, estando no estado q e lendo o síımbolo a na fita de entrada, o autômato muda para o estado p e avança o cabeçote uma posição. 06/09/06 Ricardo Silveira 1021 M= (Σ, Q, δ, q0,F) ∑ alfabeto de símbolos de entrada; Q conjunto de estados possíveis do autômato, o qual é finito; δ programa ou função de transição: δ: Q x ∑ → Q q0 estado inicial, tal que q0 é elemento de Q (indicado por uma seta) F conjunto de estados finais, tal que F está contido em Q; a estado anterior novo estado p q símbolo lido Represertação de autômato como grafo 06/09/06 Ricardo Silveira 11 Exemplo ● M = ({q0, q1, q2}, {a; b}, δ, q0, {q2}), – δ(q0; a) = q1, – δ(q1; a) = q1, – δ(q1; b) = q2. – Logo, T(M) = {anb | n ≥ 1 }. 06/09/06 Ricardo Silveira 12 Tabela de transição de estados ● Uma terceira forma de representar um AF: – Tabela indicando na vertical os estados, e na horizontal os síımbolos do alfabeto. – No cruzamento estão as transições possíveis; – O estado inicial é indicado por uma seta, e os estados finais por asteriscos. δ a b →q0 q1 - q1 q1 q2 *q2 - - 06/09/06 Ricardo Silveira 13 δ a b q0 q1 q2 q1 qf q2 q2 q1 qf qf qf qf q0 q2q1 qf a b b a,b a a b δ1 é representada na tabela Exemplo de AFD – Considere a linguagem:L1={w | w possui aa ou bb como subpalavra} ● AF: M1=({a,b},{q0,q1,q2,qf}, δ 1 , q0, {qf}) 06/09/06 Ricardo Silveira 14 δ 0 1 →*q0 q0 q1 *q1 q0 - 0 1 δ1 é representada na tabela Exemplo de AFD – Considere a linguagemconstituída por sentenças em {0; 1}* as quais não contém dois ou mais 1’s consecutivos ● AF: M1=({0,1},{q0,q1}, δ, q0, {q0,q1}) ● δ(q0; 0) = q0, δ(q0; 1) = q1, δ(q1; 0) = q0. 0 q1q0 06/09/06 Ricardo Silveira 15 M= (Σ, Q, δ, q0,F) ∑ alfabeto de símbolos de entrada; Q conjunto de estados possíveis do autômato, o qual é finito; δ programa ou função de transição: δ: Q x ∑ → 2Q q0 estado inicial, tal que q0 é elemento de Q F conjunto de estados finais, tal que F está contido em Q; p p1 a estado anterior Conjunto de novos estados símbolo lido p2 pn aa Autômato Finito Não-Determinístico 06/09/06 Ricardo Silveira 16 δ a b q0 {q0,q1} {q0, q2} q1 {qf} - q2 - {qf} qf {qf} {qf} q0 q2q1 qf a b b a,b a δ1 é representada na tabela Exemplo de AFND – Considere a linguagem:L1={w | w possui aa ou bb como subpalavra} ● AF: M1=({a,b},{q0,q1,q2,qf}, δ 2 , q0, {qf}) a,b 06/09/06 Ricardo Silveira 17 Exemplo de AFND 06/09/06 Ricardo Silveira 18 Equivalência entre AFD e AFND ● A partir de um AFND é possível construir um AFD 06/09/06 Ricardo Silveira 19 Determinismo X Não-determinismo ● Muitas vezes é mais fácil desenvolver um AFN do que um AFD – exemplo ● { w | o quinto símbolo da direita para a esquerda de w é a } ● solução determinista: não é trivial; número grande de estados ● solução não-determinista: bem simples, poucos estados ● Alternativa para construir um AFD – desenvolver inicialmente AFN 06/09/06 Ricardo Silveira 20 Exemplo ● M6 = ({ a, b }, { q0, q1, q2, qf }, δ6, q0, { qf }) 06/09/06 Ricardo Silveira 21 Exemplo ● Tabela de transição de estados do AFD 06/09/06 Ricardo Silveira 22 Exemplo ● Grafo do AFD resultante do AFN 06/09/06 Ricardo Silveira 23 Exemplo ● Dado o AFND M = ({q0, q1}, {0, 1}, δ, q0, {q1}) e – δ(q0, 0) = {q0, q1} – δ(q0; 1) = {q1} – δ(q0; 1) = φ; – δ(q1; 1) = {q0, q1} ● Construir o AFD M0 equivalente. 06/09/06 Ricardo Silveira 24 Exemplo ● Tabela do AFND Tabela do AFD 06/09/06 Ricardo Silveira 25 M= (Σ, Q, δ, q0,F) ∑ alfabeto de símbolos de entrada; Q conjunto de estados possíveis do autômato, o qual é finito; δ programa ou função de transição: δ: Q x (∑ U {ε}) → 2Q q0 estado inicial, tal que q0 é elemento de Q F conjunto de estados finais, tal que F está contido em Q; p p1 a estado anterior Conjunto de novos estados símbolo lido p2 pn aε Autômato Finito com Movimentos Vazios AFε 06/09/06 Ricardo Silveira 26 Diagrama de um AFε 06/09/06 Ricardo Silveira 27 Exemplo 06/09/06 Ricardo Silveira 28 Exemplo q 0 q 1 q 2 q 3 q 5 q 4 0,1, ..., 9 0,1, ..., 9 0,1, ..., 9 0,1, ..., 9 .● Um AFε que aceita numeros decimais compostos por um sinal opcional (+ ou -) e digitos separados por um ponto decimal ε,+,- . 06/09/06 Ricardo Silveira 29 Computação vazia 06/09/06 Ricardo Silveira 30 Exemplo 06/09/06 Ricardo Silveira 31 Computaçao nos AFε 06/09/06 Ricardo Silveira 32 Computaçao nos AFε ● Função Programa Estendida (computação) – M= (Σ, Q, δ, q0,F) 06/09/06 Ricardo Silveira 33 Exemplo 06/09/06 Ricardo Silveira 34 Exemplo 06/09/06 Ricardo Silveira 35 Equivalência entre AFN e AFε ● construção de uma função programa sem movimentos vazios ● conjunto de estados destino de cada transição não- vazia – ampliado com os demais estados possíveis de serem atingidos exclusivamente por transições vazias 06/09/06 Ricardo Silveira 36 Equivalência entre AFN e AFε 06/09/06 Ricardo Silveira 3730 Expressões Regulares X Linguagens Regulares ● Se r é uma expressão regular ela foi gerada por uma LR; ● Uma linguagem é regular, se e somente se, é possível construir um AF (AFD, AFND, AFε ) que reconheça a linguagem. ● Portanto, para determinar que uma expressão é regular deve-se construir um AF a partir dela. 06/09/06 Ricardo Silveira 3830 Expressões Regulares X Linguagens Regulares 06/09/06 Ricardo Silveira 3930 Expressões Regulares X Linguagens Regulares 06/09/06 Ricardo Silveira 4030 Expressões Regulares X Linguagens Regulares 06/09/06 Ricardo Silveira 4130 Expressões Regulares X Linguagens Regulares 06/09/06 Ricardo Silveira 4230 Expressões Regulares X Linguagens Regulares 06/09/06 Ricardo Silveira 43 Exemplo 06/09/06 Ricardo Silveira 44 Exemplo 06/09/06 Ricardo Silveira 45 Exemplo 06/09/06 Ricardo Silveira 46 Gramática Regular → Linguagem Regular 06/09/06 Ricardo Silveira 47 Gramática Regular → Linguagem Regular 06/09/06 Ricardo Silveira 48 Construção de um AFε a partir de uma GR 06/09/06 Ricardo Silveira 49 Construção de um AFε a partir de uma GR 06/09/06 Ricardo Silveira 50 Linguagem Regular → GramáticaRegular 06/09/06 Ricardo Silveira 51 Linguagem Regular → GramáticaRegular 06/09/06 Ricardo Silveira 52 Construção de uma GR a partir de um AFε 06/09/06 Ricardo Silveira 53 Construção de uma GR a partir de um AFε
Compartilhar