Baixe o app para aproveitar ainda mais
Prévia do material em texto
DCC013 Linguagens Formais e Autômatos Linguagens Regulares Tipos de Gramáticas – segundo a hierarquia de Chomsky existem quatro tipos: Tipo 0 ou Irrestritas: P = { | (NT)+, (NT)* } Tipo 1 ou Sensível ao Contexto P = { | ||||, (NT)+, (NT)+}.Exceto S Tipo 2 ou Livre de Contexto P = { A | AN, (NT)+}. Exceto S Tipo 3 ou Regular AaB ou Aa, ou seja: P = { AaX | AN, aT, XN{}} Linguagens Regulares - Preliminares 2 Tipo 3 Tipo 2 Tipo 1 Tipo 0 T+ (GR) (GLC) (GSC) (GI) Linguagens Regulares - Preliminares 3 Esquematicamente: Regulares(3) Livres de Contexto(2) Sensíveis ao Contexto(1) Irrestrita(0) Exemplo G = ({S, A, B}, {a, b}, P, S), onde P = { S aB | bA A a | aS | bAA B b | bS | aBB } 1) Qual o tipo de G? 2) L(G)? Linguagens Regulares - Preliminares 4 Livre de contexto; L(G) é o conjunto de todas as palavras em T+ que tem o mesmo número de a’s e b’s. Exemplo G = ({S, B}, {a, b}, P, S), onde P = { S aS | bB | a | b B bB | b } 1) Qual o tipo de G? 2) L(G)? Linguagens Regulares - Preliminares 5 Regular L(G) é o conjunto de todas as palavras em T+ onde todos a’s precedem todos os b’s. O autômato finito (AF) é uma máquina abstrata que reconhece linguagens regulares; Modelo matemático com entradas e saídas. Se é fornecido ao AF uma sequência de símbolos como entrada, ele responderá se esta sequência pertence a linguagem ou não; O AF pode assumir um número finito de estados; Um estado resume os estados anteriores pelos quais passou e os símbolos que já foram lidos na entrada. Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 6 Um autômato finito, pode ser vista como uma máquina composta basicamente por três partes Fita: Dispositivo de entrada que contém a informação a ser processada. A fita é finita à esquerda e à direita Unidade de Controle: Reflete o estado corrente da máquina. Possui uma unidade de leitura (cabeça de leitura), que acessa uma unidade da fita de cada vez. Após cada leitura a cabeça move-se uma célula para a direita Programa ou Função de Transição: Função que comanda as leituras e define o estado da máquina. Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 7 Autômato Finito como uma máquina com controle finito (fita, controle e função de transição): Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 8 Fita a a b c c b a a q Controle Cabeçote de leitura Estado corrente Função de transição Def. Formal de autômato finito determinístico (AFD). Um AFD é um quíntupla (, Q, , q0, F): Q : conjunto finito de estados : alfabeto q0 Q: estado inicial F Q: conjunto de estados finais : função de transições, :Q Q Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 9 A função programa de um AFD pode ser representada como um grafo orientado finito Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 10 Uma transição Estado inicial Estado final p q Estado anterior Novo estado a q0 qf qf Exemplo: autômato finito determinístico M1 = ({a, b}, {q0, q1, q2, qf}, 1, q0, {qf}) L(M1) = {w | w possui aa ou bb como subpalavra} Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 11 1 a b * q0 q1 q2 qf q1 qf q1 qf q2 q2 qf qf q1 q2 b a q0 qf a a a b b b 1 Exemplo: M2 = ({0, 1}, { q1, q2, q3}, 2, q1, {q2}). L(M2) = {w | w contém pelo menos um 1 e um número par de 0s segue o último 1} Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 12 2 0 1 q1 q2 q3 q1 q3 q2 q2 q2 – q1 1 0 0 1 0 q2 q3 * 2 Exemplo: M3 = ({0, 1}, { q1, q2}, 3, q1, {q2}) L(M3) = {w | w termina com um 1} Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 13 3 0 1 q1 q2 q1 q1 q2 q2 * 3 q1 0 0 1 q2 1 Exemplo: M4 = ({a, b}, {s, q1, q2, r1, r2}, 4, s, {r1, q1}) L(M4) = {w | w começa e termina com o mesmo símbolo} Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 14 q2 b b a a 4 s r1 q1 r2 a a b b b a Exemplo: N = ({a, b}, {q0, q1, q2}, , q0, {q2}) Transições: (q0, a) = q1, (q1, a) = q1, (q1, b) = q2. Logo, L(N) = {anb | n1} Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 15 q0 a a b q2 q1 Exemplo: Que linguagem aceita A2? Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 16 A2 q2 1 0 0 1 q3 q1 q2 0 0 1 1 Exemplo: Que linguagem aceita A3? Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 17 q0 0 1 1 q2 q1 A3 q0 1 0 0 0 1 Definição Formal de Computação: Sejam 𝐴 = 𝑄,, 𝛿, 𝑞0, 𝐹 um AFD e 𝑤 = 𝑤1𝑤2𝑤3 … 𝑤𝑛 uma palavra sobre . Dizemos que A aceita 𝑤 se existe uma sequência de estados de 𝑄, 𝑟 = 𝑟0, 𝑟1, … , 𝑟𝑛, tal que: 1. 𝑟0 = 𝑞0; e 2. 𝛿 𝑟𝑖 , 𝑤𝑖+1 = 𝑟𝑖+1 para todo 0 ≤ 𝑖 ≤ 𝑛 − 1; e 3. 𝑟𝑛 ∈ 𝐹. A sequência 𝑟 é chamada de trajetória de 𝐴 sobre 𝑤. Ou computação de 𝑤 sobre A. A linguagem aceita por um AFD A é 𝐿 𝐴 = 𝑤|𝐴 aceita 𝑤 Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 18 Extensão da função para o domínio 𝑄 × Σ∗ 1. 𝛿 𝑞, 𝜀 = 𝑞; 2. 𝛿 𝑞, 𝑎𝑢 = 𝛿 𝛿 𝑞, 𝑢 , 𝑎 para 𝑎 ∈ Σ e 𝑢 ∈ Σ∗. 𝛿 𝑞, 𝑢 = 𝑝 significa que M, iniciando no estado 𝑞, e tendo a sequência 𝑢 na fita de entrada, entrará no estado 𝑝, após o cabeçote mover-se para a direita 𝑢 células; Uma sentença é aceita por 𝑀 se 𝛿 𝑞0, 𝑢 = 𝑝 para algum 𝑝 ∈ 𝐹, ou seja 𝐿 𝑀 = 𝑢|𝛿 𝑞0, 𝑢 = 𝑝 com 𝑝 ∈ 𝐹 Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 19 Exemplo: Seja 𝐴2 = 𝑄, Σ, 𝛿, 𝑞0, 𝐹 , onde: Q = 𝑞0, 𝑞1, 𝑞2, 𝑞3 , Σ = 0,1 , F = 𝑞0 𝛿 𝑞0, 0 = 𝑞2 𝛿 𝑞1, 0 = 𝑞3 𝛿 𝑞2, 0 = 𝑞0 𝛿 𝑞3, 0 = 𝑞1 𝛿 𝑞0, 1 = 𝑞1 𝛿 𝑞1, 1 = 𝑞0 𝛿 𝑞2, 1 = 𝑞3 𝛿 𝑞3, 1 = 𝑞2 Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 20 𝐴2 q2 1 0 0 1 q1 q0 q3 0 0 1 1 Exemplo: Reconhecimento da cadeia 𝑤 Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 21 𝑤 = 110101 𝛿 𝑞0, 110101 ⇒ 𝛿 𝑞1, 10101 ⇒ 𝛿 𝑞0, 0101 ⇒ 𝛿 𝑞2, 101 ⇒ 𝛿 𝑞3, 01 ⇒ 𝛿 𝑞1, 1 ⇒ 𝛿 𝑞0, 𝜀 ⇒ 𝑞0 𝑤 = 1011 𝛿 𝑞0, 1011 ⇒ 𝛿 𝑞1, 011 ⇒ 𝛿 𝑞3, 11 ⇒ 𝛿 𝑞2, 1 ⇒ 𝛿 𝑞3, 𝜀 ⇒ 𝑞3 Logo, 𝟏𝟎𝟏𝟏 ∉ 𝐋 𝐀𝟐 . Logo, 𝟏𝟏𝟎𝟏𝟎𝟏 ∈ 𝐋 𝐀𝟐 . Discussão: o que é Determinismo? Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 22 4 2 1 0 3 0 1 1 1 1 0 0 Para todo AFD A e para toda palavra 𝑤 ∈ Σ∗ , existe exatamente uma trajetória de A sobre 𝑤. Definição: Linguagens Regulares ou do Tipo 3. Uma linguagem aceita por um autômatofinito é uma Linguagem Regular ou do Tipo 3. Exercício. Desenvolver AFDs que reconheçam as seguintes linguagens sobre = {a, b}: 1. {w | termina com aa} 2. {w | w possui aaa como subpalavra} 3. {w | w possui um número ímpar de a e b} 4. {w | w possui número par de a e ímpar de b ou vice-versa} 5. {w | o quinto símbolo da esquerda para a direita de w é a} Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 23 Exercício. Desenvolver AFDs que reconheçam as seguintes linguagens sobre = {a, b}: 6. {w | w possui aa ou bb como subpalavra} 7. {w | w não contém dois ou mais 1’s consecutivos} 8. {w | |w| mod 3 = 0} Desenvolver AFDs para as linguagens: 1.Identificadores de linguagens de programação 2.Inteiros com ou sem sinal (+ ou -) 3.Reais com ou sem sinal (+ ou -). Pode haver ou não dígitos após a , (vírgula). Ex: 45; 58,6; -54.; +.859 Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 24 Autômato Finito Não-Determinístico (AFND ou AFN) Não-determinismo é uma importante generalização dos AF’s, essencial para a teoria da computação e para a teoria das linguagens formais. Qualquer AFND pode ser simulado por um autômato finito determinístico Em AFNDs, a função programa leva de um par (estado, símbolo) a um conjunto de estados possíveis. Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 25 Pode-se entender que o AFN assume simultaneamente todas as alternativas de estados possíveis {p0, p1, ..., pn} a partir do estado atual q Q e do símbolo recebido a ; Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 26 Exemplo de transições não determinística p p2 p3 a p1 a a ⋯ Definição: Autômato Finito Não- Determinístico. Um AFN é uma quíntupla 𝑀 = Σ, 𝑄, 𝛿, 𝑞0, 𝐹 , onde: Σ : alfabeto de símbolos de entrada; 𝑄 ≠ ∅ : conjunto finito de estados; 𝛿 : função programa ou função de transição 𝛿: 𝑄 × Σ → 2 𝑄 𝑞0 ∈ 𝑄: estado inicial; 𝐹 ⊂ 𝑄 - conjunto de estados finais. Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 27 Portanto, os componentes do AFND são os mesmos do AFD, com exceção da função programa: Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 28 p p2 p3 a p1 a a ⋯ Exemplo: AFND M5 = ({a, b}, {q0, q1, q2, qf}, 5, q0, {qf}): M5 reconhece a linguagem L(M5) = {w | w possui aa ou bb como sub-palavra} Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 29 5 a b q0 q1 q2 Qf {q0, q1} {qf} - {qf} {q0, q2} - {qf} {qf} * q0 q1 qf q2 a a,b b a a,b b Exemplo: AFN M6 = ({a,b}, {q0, q1, q2, qf}, 6, q0, {qf}): M6 reconhece a linguagem : 𝐿 𝑀6 = 𝑤𝑎𝑎𝑎|𝑤 ∈ 𝑎, 𝑏 ∗ 𝐿 𝑀6 = 𝑤|𝑤 ∈ 𝑎, 𝑏 ∗ e 𝑤 termina com 𝑎𝑎𝑎 Linguagens Regulares – Gramáticas Regulares e Autômatos Finitos 30 q0 a a qf q1 M6 q2 a b a
Compartilhar