Reverso de uma Linguagem Regular 1 Teorema: R reverso L de uma linguagem regular é uma linguagem regular L Idéia da prova: Construa um NFA que aceita R L : inverta as transições do NFA que aceita L 2 Prova Como L é regular, existe um NFA que aceita L Exemplo: b L ab * ba a b a 3 Inverta as Transições b a b a 4 Torne o antigo estado inicial o estado final b a b a 5 Adicione um novo estado inicial b a b a 6 A máquina resultante aceita R L R L é regular L ab * ba b L b * a ab R a b a 7 Gramáticas 8 Gramáticas Gramáticas expressam linguagens Exemplo: Inglês sentence noun _ phrase noun _ phrase article predicate verb predicate noun 9 article a article the noun boy noun dog verb runs verb walks 10 Uma derivação de “the boy walks”: sentence noun _ phrase predicate noun _ phrase verb article verb noun the noun verb the boy verb the boy walks 11 Uma derivação de “a dog runs”: sentence noun _ phrase predicate noun _ phrase verb article noun verb a noun verb a dog verb a dog runs 12 Linguagem da gramática: L = { “a boy runs”, “a boy walks”, “the boy runs”, “the boy walks”, “a dog runs”, “a dog walks”, “the dog runs”, “the dog walks” } 13 Notação noun boy noun dog Variável ou Não terminal Regra de Produção Terminal 14 Outro Exemplo Gramática: S aSb S Derivação da sentença ab: S aSb ab S aSb S 15 Gramática: S aSb S Derivação da sentença aabb: S aSb aaSbb aabb S aSb S 16 Outras derivações: S aSb aaSbb aaaSbbb aaabbb S aSb aaSbb aaaSbbb aaaaSbbbb aaaabbbb 17 Linguagem da gramática S aSb S L {a b : n 0} n n 18 Mais Notação Gramática G = (V, S, S, P) V : Conjunto de variáveis S: Conjunto de símbolos terminais S : Variável inicial P: Conjunto de regras de produção 19 Exemplo Gramática G : S aSb S G V ,T , S , P V {S} T {a, b} P {S aSb, S } 20 Mais Notação Forma Sentencial: Uma sentença que contém variáveis e terminais Exemplo: S aSb aaSbb aaaSbbb aaabbb forma sentencial sentença 21 Escrevemos: * S aaabbb Como abreviação de: S aSb aaSbb aaaSbbb aaabbb 22 De modo geral: Se: * w1 wn w1 w2 w3 wn 23 Por default: * w w 24 Exemplo Gramática S aSb S Derivações * S * S ab * S aabb * S aaabbb 25 Exemplo Gramática S aSb S Derivações S aaSbb aaSbb aaaaaSbbbbb 26 Outro Exemplo de Gramática Gramática G : S Ab A aAb A Derivações: S Þ Ab Þ b S Þ Ab Þ aAbb Þ abb S Þ Ab Þ aAbb Þ aaAbbb Þ aabbb 27 Mais Derivações S Ab aAbb aaAbbb aaaAbbbb aaaaAbbbbb aaaabbbbb S aaaabbbbb S aaaaaabbbbbbb S a b b n n 28 Linguagem de uma Gramática Para uma gramática com variável inicial G S: L(G ) {w : S w} String de terminais 29 Exemplo Gramática S Ab G: A aAb A L(G) = {a b n n+1 Já que: : n ³ 0} S a b b n n 30 Uma Notação Conveniente A aAb A article a article the A aAb | article a | the 31 Gramáticas Lineares 32 Gramáticas Lineares Gramáticas com no máximo uma variável do lado direito de cada produção Exemplos: S aSb S Ab S A aAb A 33 Uma Gramática Não-Linear Gramática G: S SS S S aSb S bSa L(G) {w : na (w) nb (w)} 34 Outra Gramática Linear Gramática G: SA A aB | B Ab L(G ) {a b : n 0} n n 35 Gramática Linear à Direita Todas as produções têm a forma: A xB ou A x Exemplo: S abS S a 36 Gramática Linear à Esquerda Todas as produções têm a forma: A Bx ou A x Exemplo: S Aab A Aab | B Ba 37 Gramáticas Regulares 38 Gramáticas Regulares Uma gramática regular é qualquer gramática linear à direita ou à esquerda Exemplos: G1 G2 S abS S Aab S a A Aab | B Ba 39 Observação Gramáticas regulares geram linguagens regulares Exemplos: G2 G1 S Aab S abS A Aab | B S a Ba L(G1) (ab) * a + L(G2 ) = a(ab) 40 Gramáticas Regulares Geram Linguagens Regulares 41 Teorema Linguagens Geradas por Gramáticas Regulares Linguagens Regulares 42 Teorema - Parte 1 Linguagens Geradas por Gramáticas Regulares Linguagens Regulares Toda gramática regular gera uma linguagem regular 43 Teorema - Parte 2 Linguagens Geradas por Gramáticas Regulares Linguagens Regulares Toda linguagem regular é gerada por uma gramática regular 44 Prova – Parte 1 Linguagens Geradas por Gramáticas Regulares Linguagens egulares A linguagem L(G ) gerada por umq gramática regular G é regular 45 O caso de Gramáticas Lineares à Direita Seja G uma gramática linear à direita Vamos provar : L(G ) é regular Idéia da Prova: Vamos construir um NFA com L( M ) L(G ) M 46 Gramática Exemplo: G é linear à direita S aA | B A aa B Bb B|a 47 Construa o NFA M tal que todo estado é uma variável da gramática: A S S aA | B A aa B Bb B|a VF B estado final especial 48 Adicione arcos para cada produção: a A S VF B S aA 49 a S A VF B S aA | B 50 A a a S a VF B S aA | B A aa B 51 A a a S S aA | B A aa B B bB VF a B b 52 A a a S S aA | B A aa B B bB | a a VF a B b 53 A a a S a VF a B b S aA aaaB aaabB aaaba 54 NFA Gramática M a G S aA | B a B bB | a A a S A aa B VF a B b L( M ) L(G ) aaab * a b * a 55 Em Geral Dada uma gramática linear à direita G com variáveis V0 ,V1,V2,… ,Vn e produções: Vi a1a2 amV j ou Vi a1a2 am 56 Construímos o NFA cada variável Vi V1 M tal que: corresponde a um estado: V3 V0 VF V2 V4 estado final especial 57 Para cada produção: Vi a1a2 amV j adicionamos transições e os estados intermediários requeridos Vi a1 a2 ……… am V j 58 Para cada produção: Vi a1a2 am adicionamos transições e os estados intermediários requeridos Vi a1 a2 ……… am VF 59 O NFA M resultante tem a forma: a9 a1 V0 a2 V1 a3 V3 a5 a4 a3 V2 Temos que: a4 a5 a8 V4 a9 VF L(G) L( M ) 60 O caso de Gramática Linear à Esquerda Seja G uma gramática linear à esquerda Vamos provar: L(G ) é regular Idéia da Prova : Construir uma gramática linear à R direita G com L(G ) L(G) 61 Como G é uma gramática linear à esquerda as produções são da forma: A Ba1a2 ak A a1a2 ak 62 Construindo a gramática linear à direita Em G : G A Ba1a2 ak A ® Bv Em G : A ak a2a1B Av B R 63 Construindo a gramática linear à direita em G : G A a1a2 ak Av Em G : A ak a2a1 Av R 64 L(G ) L(G) É fácil ver que: Como R G é linear à direita, temos: L(G) L(G) Linguagem Regular Linguagem Regular R L(G ) Linguagem Regular 65 Prova - Parte 2 Linguagens Geradas por Gramáticas Regulares Linguagens Regulares Toda linguagem regular L é gerada por uma gramática regular G 66 Toda linguagem regular L é gerada por uma gramática regular G Idéia da Prova : Seja M um NFA com L L(M ). Construa, a apartir de M uma gramática regular G tal que L( M ) L(G ) 67 Como L é regular existe um NFA M tal que L L(M ) b Exemplo: M q0 a q1 a L ab * ab(b * ab) * L L(M ) q2 b q3 68 Convertendo M em uma gramática b linear à direita M q0 q0 aq1 a q1 a q2 b q3 69 b M q0 q0 aq1 q1 bq1 q1 aq2 a q1 a q2 b q3 70 b M q0 aq1 q1 bq1 q1 aq2 q0 a q1 a q2 b q3 q2 bq3 71 L(G ) L( M ) L b G q0 aq1 q1 bq1 q1 aq2 q2 bq3 M q0 a q1 a q2 b q3 q3 q1 q3 72 Em Geral a Para cada transição: q Adicione a produção: q ap variável terminal p variável 73 Para cada estado final: qf Adicione a produção: qf 74 Como G é uma gramática linear à direta G é também uma gramática regular com L(G ) L( M ) L 75