Notas de Aula - Elementos de Linguagens Formais e Autômatos

UNIVERSIDADE PRESBITERIANA MACKENZIE NOTAS DE AULA Elementos de LINGUAGENS FORMAIS E AUTÔMATOS Distribuição restrita para uso próprio dos alunos Pedro Paulo Balbi de Oliveira pedrobmackenziebr professormackenziebrpedrob 24 de outubro de 2022 2 UNIDADE 1 REVISÃO DE CONJUNTOS 11 DEFINIÇÕES GERAIS Def 11 CONJUNTO uma coleção qualquer de elementos a Î A a pertence a A a Ï A a não pertence a A A a1 a2 an Û a1 Î A a2 Î A an Î A Ex ℕ 1 2 3 NATURAIS ℤ 3 2 1 0 1 2 3 INTEIROS ℚ números da forma ij i j Î ℤ j ¹ 0 RACIONAIS Def 12 CARDINALIDADE Número de elementos do conjunto A Def 13 CONJUNTO VAZIO Conjunto que não tem elementos Æ Æ º Obs 1 Æ 0 Obs 2 Especificação de conjuntos x 3 2 1 0 1 2 3 x x Î ℤ 3 x 3 x Î ℤ 3 x 3 Obs 3 ℝ ℙ primos ℕ ℤ ℚ π ℝ reais ℂ complexos 3 Def 14 IGUALDADE A B Û x Î A Û x Î B Def 15 SUBCONJUNTO A Í B se a Î A Þ a Î B caso contrário A Ë B Obs 1 A Ì B A está contido em B B É A B contém A Obs 2 SUBCONJUNTO PRÓPRIO A Ì B A é subconjunto de B mas A¹B Obs 3 A B Û A Ì B e B Ì A Æ Ì A Obs 4 A Þ A Ì A Def 16 CONJUNTO POTÊNCIA Power Set Conjunto de todos os subconjuntos de um conjunto A Representação 2A Ex A 1 2 3 2A Æ 1 2 3 12 13 23 123 Obs A a1 a2 an 2A 2n Def 17 COMPLEMENTO A u u Ï A OBS u Î U conjunto universo Def 18 DIFERENÇA RELATIVA A B a a Î A a Ï B A B Def 19 UNIÃO A È B u u Î A u Î B A B 4 Def 110 INTERSECÇÃO A Ç B u u Î A u Î B Def 111 CONJUNTO DISJUNTOS A Ç B Æ A e B são disjuntos Def 112 DIAGRAMA DE VENN U conjunto universo OBS Leis de Morgan Def 113 PARTIÇÃO p Ai i Î K K é um conjunto de índices arbitrários p é uma partição de A se todo elemento de A está exatamente em dos Ai Obs Os Ai são os blocos da partição pA A1 A2 A3 A4 A5 pB B1 B2 B3 B4 B5 B6 B7 pB refina pA Û todos Bj Ì Ai B A B A B A B A È Ç Ç È A U U U U A B A B A B A A B A B A B ou A B B A A3 B3 A2 B2 B4 B7 A5 B6 A1 B1 A4 B5 5 Def 114 R TUPLA Seqüência ordenada escrita na forma a1 a2 ar O iésimo termo Þ iésima coordenada Se r 2 Þ par ordenado Def 115 PRODUTO CARTESIANO A1 A2 Ar conjunto qualquer Produto cartesiano todas as rtuplas a1 a2 ar tal que a1 Î A1 a2 Î A2 ar Î Ar Representação A1 A2 Ar Se os Ai são idênticos A1 A2 Ar Ar Ex A 0 1 e B 1 2 3 A B 01 02 03 11 12 13 B A 10 11 20 21 30 31 A A A2 00 01 11 10 12 RELAÇÕES Def 116 RELAÇÃO subconjunto do produto cartesiano A1 A2 Ar RELAÇÃO BINÁRIA Quando r 2 temse os subconjuntos de A1 A2 xy x Î A1 e y Î A2 Notação R é uma relação de A em B Þ ab Î R a é relacionado com b Þ a R b se x y Î R x R y ou y R x Ex A 2 3 4 e B 2 3 4 5 6 Seja R de A em B a R b Û a divide b ou seja restoba 0 R 2 2 24 26 33 36 44 6 Obs Representação de uma relação binária como grafo R 00 03 32 23 20 21 Def 117 DOMÍNIO a Î A a R b existe para algum b Def 118 CONTRADOMÍNIO b Î B a R b existe para algum a Ex R 22 24 26 33 36 44 Domínio 2 3 4 elementos de A usados em R Contradomínio 2 3 4 6 elementos de B usados em R Def 119 RELAÇÃO INVERSA Ř se R é de A em B então Ř é de B em A tal que b Ř a Û a R b Ou seja os pares de Ř são os pares de R em ordem inversa Ex A 2 3 4 B 2 3 4 5 6 seja Ř b Ř a Û a divide b R 22 42 62 33 63 44 3 2 0 1 7 Def 120 COMPOSIÇÃO DE RELAÇÕES R1 de A1 em A2 R1 R 2 de A1 em A3 tal que ai R1 R2 aj ou R1 R2 ai aj R2 de A2 em A3 sse ak Î A2 Þ ai R1 ak ak R2 aj Ex A1 1 2 3 4 A2 2 3 4 A3 1 2 3 R1 ai ak ai ak 6 24 33 42 R2 ax aj ak aj 1 32 43 21 R1 R2 23 32 41 Þ ai aj ai aj 5 Pois ai ak 6 Þ ai 1 aj 6 ai aj 5 A1 A2 A3 R1 R2 R1 R2 R1 R2 A2 0 0 0 0 0 1 0 1 0 1 0 0 2 3 4 1 2 3 4 A1 R1 A2 0 0 0 0 0 1 0 1 0 1 0 0 1 2 3 1 2 3 4 A1 R1 o R2 1 0 0 0 1 0 0 0 1 2 3 4 A2 A3 R2 1 2 3 8 Def 121 RELAÇÃO REFLEXIVA ai Î A ai R ai Ex Divide Def 122 RELAÇÃO SIMÉTRICA ai aj Î A ai R aj Þ aj R ai Ex Ser irmão de Def 123 RELAÇÃO TRANSITIVA ai aj ak Î A ai R aj aj R ak Þ ai R ak Ex Maior do que Def 124 RELAÇÃO DE ORDEM TOTAL Relação tal que ai aj Î A Þ ai R aj aj R ai1 Quando isso não acontece Þ RELAÇÃO DE ORDEM PARCIAL Ex 1 ℝ é totalmente ordenado pela relação Ex 2 A relação definida sobre um conjunto de inteiros onde ij Û j um divisor de i é uma ROP A 2 3 4 6 8 12 36 60 ai ai aj ak ai aj 12 60 36 4 6 3 2 8 j i ij j é divisor de i 9 13 RELAÇÕES DE EQUIVALÊNCIA Def 125 Uma relação binária R sobre S é uma RELAÇÃO DE EQUIVALÊNCIA se 1 R é reflexiva 2 R é simétrica 3 R é transitiva Exemplos 1 Seja a relação binária Ri definida sobre o conjunto ℋ dos seres humanos tal que i Ri j ó i é irmão de j Ri não é uma relação de equivalência Por que 2 Seja R de A em B a R b Û a divide b R não é uma relação de equivalência Por que TEOREMA 11 Se R é uma relação de equivalência sobre S então é possível dividir S em K subconjuntos distintos K 1 chamados de CLASSES DE EQUIVALÊNCIA tais que a R b Û a e b pertencem ao mesmo conjunto Em outras palavras uma relação de equivalência R sobre S induz uma partição de S Exemplo Seja Rs definida sobre o conjunto ℋ dos seres humanos tal que i Rs j ó i é do mesmo sexo que j Rs é uma relação de equivalência Se sim represente a partição Ps induzida por Rs no conjunto ℋ Def 126 O índice de uma relação de equivalência R representado por i R é o número de classes de equivalência de R Def 127 Sejam R1 e R2 relações de equivalência R1 refina R2 se R1 Í R2 isto é x R1 y Þ x R2 y Obs se R1 refina R2 então i R1 ³ i R2 10 14 FUNÇÕES Def 1 25 FUNÇÃO É uma regra que designa para cada ai Î A um único bi Î B f A B Domínio à Contradomínio Notação xy Î f y fx x f y Ex f ℝ ℝ y fx x 1 Se x ³ 0 Þ y ³ 1 Imagem Função de r variáveis f a1 a2 ar f A1 A2 Ar B Com r2 z x y x Î ℝ y Î ℝ função do tipo ℝ ℝ ℝ ou ℝ2 ℝ Def 126 INJEÇÃO Para quaisquer 2 elementos de A correspondem 2 elementos distintos em B y x y x 2 y para cada x 11 Def 127 SOBREJEÇÃO Esgota B Def 128 BIJEÇÃO Acontece injeção e sobrejeção OBS Somente a bijeção aceita inversa f1 é inversa de f Ex y ax b Þ Inversa x y ba Fonte dos diagramas wwwtodoestudocombr Def 129 COMPOSIÇÃO DE FUNCÕES h f g gf fx senx hx e sen x gx e x C A B F G 12 UNIDADE 2 LINGUAGENS GRAMÁTICAS E RECONHECEDORES 21 ALFABETOS E LINGUAGENS Def 21 Um alfabeto ou vocabulário å é um conjunto finito não vazio de símbolos Def 22 Uma palavra ou cadeia ou string sobre um alfabeto å é uma seqüência finita de símbolos de å x é uma cadeia Þ x a1 a2 an n ³ 0 ai Î å i 1 2 n Quando n 0 Þ e cadeia vazia Def 23 Comprimento de uma cadeia x sobre um alfabeto å representado por x é o número de ocorrências de símbolos de å em x 011 3 nº de elementos na cadeia Ex å 0 1 Þ e 0 Def 24 Sejam x e y duas cadeias sobre å a concatenação de x e y é definida como a cadeia xy Ex å 0 1 x 010 y 10 Þ xy 01010 yx 10010 OBS1 A cadeia vazia é o elemento neutro da operação de concatenação Þ eex xe ex x OBS2 Concatenação sucessiva 10n 10101010 n ocorrências concatenadas da cadeia 10 Def 25 Sejam X e Y conjuntos de cadeias sobre å O produto de X e Y é definido por XY xy x Î X y Î Y Notação X0 e Xi1 Xi X i ³ 0 13 Operações com um conjunto X de cadeias Fechamento de Kleene Kleenes closure X Fechamento Positivo positive closure X X Xi i ³ 1 todas as concatenações possíveis X Xi i ³ 0 todas as concatenações possíveis mais a cadeia vazia Exemplo å 0 1 å e 0 1 01 10 00 11 å 0 1 01 10 00 11 Exercício Sejam å 0 1 N A B e V å È N Para cada expressão abaixo dizer se ela é falsa ou verdadeira 0 Î V AA Î V V à AA Î V e Î V B1e0B Î V B1e0B Î V 01 Î VNV A Î VNV e Î VNV 01 Î VNV 0A1 Î VNV AA Î VNV AA Î VNV 01A Î VNV AAA Î VNV Def 26 Uma linguagem L é um conjunto qualquer de cadeias sobre um alfabeto å ou seja L Ì å Como representar L Se L é finito basta listar todas as cadeias Se L é infinito existem 2 sistemas principais para representação de linguagens 1 O sistema gerador Gramática 2 O sistema reconhecedor Autômato 14 22 RECONHECEDORES E GRAMÁTICAS Um reconhecedor de L é a representação de um procedimento que quando apresentado a uma cadeia qualquer pára e responde sim após um número finito de passos caso a cadeia pertença a L ou pára e responde não caso a cadeia não pertença a L ou não pára caso a cadeia não pertença a L Simbolicamente Uma configuração do reconhecimento é uma descrição a do estado do controle finito b do conteúdo da fita de entrada e da posição da cabeça c do conteúdo da memória Um reconhecedor aceita ou reconhece uma cadeia w se 1 partindo de uma configuração inicial 2 faz uma seqüência finita de movimentos e 3 termina em uma configuração final A linguagem aceita por um reconhecedor R é LR w Î å R aceita w Fita de entrada a1 an Símbolos de å Cabeça de leitura e escrita Movimento bidirecional Memória Controle finito a2 15 Def 27 Uma gramática é uma 4upla G å N S P onde å é um conjunto finito não vazio de símbolos chamados de terminais N é um conjunto finito não vazio de símbolos chamados de nãoterminais com å Ç N Æ S Î N é o símbolo não terminal inicial P é um conjunto de regras de produção da forma a b onde a Î N È å N N È å b Î N È å Ex G å N S P onde N A S S símbolo nãoterminal inicial å a b P S ab S aASb S bSb AS bSb A e aASAb aa Exemplo de cadeias geradas por essa gramática 1 S ab 2 S aASb abSbb ababbb Ou seja a linguagem gerada LG ab ababbb OBS A linguagem gerada por G pode ser obtida pela construção da Árvore de Derivação correspondente Se L é gerada por G qualquer gramática G obtida a partir de G passa a gerar L possivelmente diferente de L Ao se projetar uma gramática que gere L devese tomar o cuidado de permitir a geração de todas e apenas as cadeias de L Exercício Construa uma gramática para cada uma das 3 linguagens abaixo Lembremse de que a gramática tem de ser capaz de gerar todas as cadeias da linguagem nem mais e nem menos L1 01n n ³ 1 01 011 0111 L2 0n1n n ³ 1 01 0011 000111 L3 Números inteiros decimais com ou sem sinal sem iniciar com zero Notação Letra maiúscula nãoterminais Letra minúscula terminais 16 Def 28 Sejam uma gramática G å N S P V N È å a Î V e b Î V a deriva diretamente b a Þ b se existem a1 a2 a b Î V tais que a a1 a a2 b a1 b a2 e a b Î P Por exemplo segundo G definido anteriormente S Þ aASb Þ abSbb Þ ababbb S ababbb Notação deriva em n passos deriva em zero ou mais passos Def 29 Sejam G å N S P e V N È å O conjunto de Formas Sentenciais de G é definido por SG a Î V S a Def 210 Sejam G å N S P e V N È å A Linguagem Gerada ou Representada por G é o conjunto LG w Î å S w å Ç SG Ou seja são todas as cadeias terminais deriváveis a partir de S OBS As formas sentenciais de uma gramática são a própria árvore de derivação associada à gramática enquanto a linguagem gerada constitui o conjunto das folhas da árvore OBS No contexto usual de linguagens de programação 1 å símbolos º palavras reservadas variáveis definidas símbolos numéricos operadores delimitadores 2 cadeia º programa sintaticamente correto 3 L linguagem º conjunto de programas sintaticamente corretos 4 G gramática º estrutura sintática 3 Þ n Þ Þ deriva diretamente não deriva diretamente Þ n Þ 17 23 HIERARQUIA DE CHOMSKY A gramática como foi definida anteriormente é chamada de gramática Irrestrita ou Tipo0 ou ainda Recursivamente Enumerável gramática SemiThue ou gramática de Estrutura de Frase Def 211 G å N S P com V N È å é gramática Sensível ao Contexto ou Tipo1 se toda produção de P é da forma A Î N 1 a A g a b g a g Î V V N È å b Î V 2 S e sendo que se esta regra de produção ocorrer S não pode aparecer no lado direito de qualquer outra produção se isto puder ocasionar redução do tamanho da cadeia da direita por exemplo uma regra de produção como S 1S não geraria problema Exemplo 1 Algumas regras de produção da primeira gramática apresentada não estão expressas na forma canônica do tipo sensível ao contexto G a b A S S P P S ab S aASb S bSb AS bSb A e aASAb aa Def 212 G å N S P é gramática Livre de Contexto ou Tipo2 se toda produção de P é da forma A b A Î N b Î V Def 213 G å N S P é uma gramática Regular ou Tipo3 se toda produção de P é da forma linear à direita rightlinear 1 A wB A B Î N 2 A w w Î å Ou da forma linear à esquerda leftlinear 3 A Bw A B Î N 4 A w w Î å 18 Exemplo 2 L1 01n n ³ 1 é regular mas G1 não evidencia o fato G1 0 1 I A I P1 P1 I 0A1 A 1A A e G2 0 1 I I P2 P2 I 01 I I1 Def 214 Uma linguagem L é do Tipox se existe uma gramática Tipox G tal que L LG isto é a linguagem L é gerada pela gramática G OBS Tipos 2 e 3 Só existe 1 nãoterminal do lado esquerdo e nenhum terminal Tipo1 Pode haver mais de 1 nãoterminal do lado esquerdo mas só 1 é transformado em cada regra de produção Tipo0 Qualquer quantidade de nãoterminais do lado esquerdo das produções 19 Hierarquia de Chomsky Relacionamento entre Gramáticas ou Linguagens e seus reconhecedores correspondentes OBS2 Uma visão mais sintética segundo Wolfram Tipo0 Produções arbitrárias MT Memória arbitrariamente grande Tipo1 Produções da forma a b tal que a b a Î N È å b Î N È å ALL Memória proporcional ao comprimento da cadeia de entrada Tipo2 Produções da forma A a tal que A Î N a Î N È å e a finito PDA Memória em pilha com uma quantidade fixa de elementos disponíveis em um dado tempo Tipo3 Produções da forma unitária A sB ou A s tal que A B Î N s Î å È e AF Memória apenas de constantes ou de quantidades indeterminadas Irrestrita Tipo 0 Recursivamente Enumerável Máquina de Turing Sensível ao Contexto Tipo1 Autômato Limitado Linearmente Livre de Contexto Tipo2 Autômato com Pilha PDA Regular Tipo3 Autômato Finito 20 UNIDADE 3 AUTÔMATOS FINITOS E LINGUAGENS REGULARES 31 AUTÔMATOS FINITOS Def 31 Um autômato finito é uma 5upla A Q å d q0 F onde Q Conjunto finito não vazio Estados å Alfabeto de entrada å Ç Q f q0 Î Q Estado inicial F Í Q Conjunto de estados finais d Q å Q Função de transição de estados Simbolicamente dq a q Û O autômato estando no estado q e lendo o símbolo a na fita de entrada move a cabeça leitora uma posição para a direita e vai para o estado q Função d estendida d Q å Q dq e q transição que não altera estado dq xa d d q x a x Î å a Î å dq x q Û O autômato estando no estado q e lendo o símbolo mais à esquerda da cadeia x vai estar no estado q após todos os símbolos de x terem sido lidos Def 32 Sejam A um autômato finito e x Î å x é aceita por A se dq0 x Î F Caso contrário dizse que a cadeia é rejeitada ou não aceita Fita de entrada a1 an Cabeça de leitura Movimento unidirecional Controle finito a2 21 Def 33 Seja A um autômato finito A linguagem reconhecida por A é LA x Î å dq0 x Î F Exemplo de um Autômato Finito AF Diagrama de Transição de Estados A Q å d q0 F A q0 q1 01 d q0 q1 Tabela de Transição de Estados dq0 0 q0 dq1 0 q1 dq0 1 q1 dq1 1 q0 Exemplos de cadeias aceitas por A 1 01 01101 Exemplos de cadeias rejeitadas por A 0 101 101101 L A x Î å x tem quantidade ímpar de 1s Exercícios Para cada uma das linguagens a seguir todas definidas sobre o alfabeto å a b construa um autômato finito que a reconheça Lembremse de que 1 O autômato criado tem de ser capaz de reconhecer todas as cadeias da linguagem nem mais e nem menos 2 As transições de estado só podem estar associadas aos símbolos do alfabeto portanto não se pode ter transição via cadeia vazia 3 De cada estado tem de sair uma e apenas uma transição de estado para cada um dos símbolos do alfabeto L1 å L2 e L3 å L4 L5 Todas as cadeias em que tanto os as quanto os bs ocorrem em quantidades pares 0 0 q1 q0 1 1 22 Def 34 Seja R relação de equivalência sobre å R é uma relação de equivalência à direita ou relação invariante à direita se xRy Þ z Î å xzRyz Ex Seja R sobre å definida por xRy Û dq0 x dq0 y xRy Þ dq0 x dq0 y q Mas dq0 xz d dq0 x z dq z d dq0 y z dq0 yz Þ xzRyz Intuitivamente R é a resposta do autômato à cadeia Def 35 Sejam R relação de equivalência sobre å e L Í å R refina L se xRy Þ x Î L Û y Î L Ou seja se R refina L L é a união de algumas ou todas as classes de equivalência de R Def 36 Seja L Í å A relação RL é definida por xRLy Û z Î å xy Î L Û yz Î L Teorema 31 1 RL é uma relação de congruência à direita 2 RL refina L 3 Se R é uma relação de congruência à direita que refina L Þ R Í RL Ou seja RL é a menor ie menor número de classes de equivalência relação de congruência à direita que refina L Teorema 32 Teorema de MyhillNerode Seja L Í å são equivalentes 1 L é regular 2 Existe uma relação de congruência à direita R sobre å que refina L e que tem índice finito 3 iRL é finito OBS Este teorema é muito útil para provar que certas linguagens não são regulares q0 q1 q2 yz z x y xz 23 32 MINIMIZAÇÃO DE AUTÔMATOS FINITOS OBS Computabilidade Performance Computabilidade Ser ou não ser capaz de computar Performance Qual a facilidade de computar gasto de memória tempo de execução esforço de codificação facilidade de manutenção etc A F Mínimo Mesma computabilidade porém melhor performance Def 37 Seja A Q å d q F Um estado q Î Q é acessível se x Î å tal que q dq0 x Def 38 O autômato conexo associado a A Q å d q F é definido por Ac Q d q0 F onde Q q Î Q q é acessível F F Ç Q d d Ç Q å Q Def 39 Dois autômatos A1 e A2 são equivalentes se L A1 LA2 Teorema 33 Para todo autômato finito A A e Ac são equivalentes A determinação de estados acessíveis pode ser mecanizada organizandose a função d em forma de árvore e verificandose os estados que ocorrem S 24 Ex Seja A onde å a b c Q 0 1 2 3 4 5 q0 0 F3 4 e d dado por d a b c 0 1 2 0 1 2 1 3 2 0 2 3 3 3 1 2 4 5 1 2 5 0 4 5 Conclusão 4 5 Não acessíveis 0 1 2 3 Acessíveis Portanto Ac Q d q0 F onde Q 0 1 2 3 F 3 å a b c q0 0 d Tabela de transição de estados d a b c 0 1 2 0 1 2 1 3 2 0 2 3 3 3 1 2 Def 310 Dois estados q e q são equivalentes qºq sse x Î å dq x Î F Û dq x Î F Consequentemente também vale que x Ï å dq x Ï F Û dq x Ï F A relação º é uma relação de equivalência Portanto ela particiona o conjunto Q de estados A importância disso é que ela permite identificar elementos redundantes de Q do ponto de vista de reconhecimento de linguagem pois se qºq q e q na mesma classe de equivalência não irá fazer diferença se o autômato se encontra no estado q ou no estado q quando uma cadeia x Î å começar a ser processada Logo o autômato pode ser minimizado escolhendose apenas um elemento de cada uma das classes de equivalência da relação º S a a c c c c b b b b a 0 1 0 3 1 2 0 2 3 3 1 2 2 a 25 Def 311 Dois estados q e q são kequivalentes q q sse x Î å x k dq x Î F Û dq x Î F OBS A relação também é uma relação de equivalência Da definição segue que se q q então q q para todo k k Portanto pk partição de Q induzida por refina pk ou seja ipk ³ ipk k k Teorema 34 Podese encontrar a relação º considerandose sucessivamente as relações e assim por diante até que pk pk1 k³0 Teorema 35 O processo a que se refere o teorema anterior sempre pára ie podese construir um algoritmo para construir a relação º Ou seja em conjunto q q Þ p0 q q Þ p1 q q Þ pk q q Þ pk1 pk Þ q º q Quando dois pk subsequentes são iguais fica determinada a equivalência OBS Uma descrição do algoritmo pode encontrada na p67 do Hopcroft Ullman ou no livro do PBlauth k º k º k º k º k º 0º 1º 2º 0 º 1 º k º 1 º k 26 Exemplo de minimização de um autômato finito A A B C D E F 01 d A E F d 0 1 A B C B E F C A A D F E E D F F D E Construção de º Partições p0 A B C D E F Estados Estados p1 A C B D E F finais não finais p2 A C B D E F p3 A C B D E F Autômato Finito Mínimo d 0 1 A BD C C A A BD EF EF EF BD EF A B C E F A A D F D E F E 01 0 1 01 EF BD C A 1 0 27 33 EXPRESSÕES REGULARES Def 312 Seja å um alfabeto As expressões regulares sobre å e os conjuntos que elas representam são definidos recursivamente como a f é uma expressão regular e representa o conjunto f b e é uma expressão regular e representa o conjunto e c Se a Î å então a é uma expressão regular e representa o conjunto a d Se r e s são expressões regulares representando respectivamente os conjuntos R e S então rs rs r e s são expressões regulares representando respectivamente R È S RS R e S OBS Para se poder eliminar alguns parênteses assumese que a prioridade das operações é 1 Fechamento de Kleene e positivo 2 Concatenação 3 Soma EXPRESSÃO REGULAR LINGUAGEM REPRESENTADA aa º a2 Somente a palavra aa aa b Somente as palavras aa e b a Todas as palavras com as concatenados ba Todas as palavras que iniciam por b seguido por zero ou mais as ab Todas as palavras sobre a b ab Todas as palavras sobre a b e também a cadeia vazia abaaab Todas as palavras contendo aa como subpalavra ababa Todas as palavras contendo exatamente 2 bs abaabb Todas as palavras que terminam com aa ou bb aebba Todas as palavras que não possuem 2 as consecutivos incluindo e a b Exercício É possível construir um autômato finito que reconheça a linguagem L 0n1n n ³ 1 28 34 AUTÔMATO FINITO NÃODETERMINÍSTICO Def 313 Um autômato finito não determinístico é uma 5upla A Q å d q0 F com Q å q0 e F definidos como no caso determinístico e d da forma d Q å 2Q onde 2Q é o conjunto potência de Q dq a q1 q2 qn Û O autômato estando no estado q e tendo o símbolo a na fita de entrada move sua cabeça leitora uma posição para a direita transitando para cada um dos qi estados i1 n conceitualmente é equivalente a imaginar que o autômato se subdivide em n cópias cada uma das quais transita para um qi distinto i1 n Exemplo Def 314 Seja x Î å x é aceita pelo AFND A Q å d q0 F se dq0 x Ç F ¹ f Ou seja algum estado final em dq0 x Portanto LA x Î å dq0 x Ç F ¹ f 1 1 1 1 0 0 0 0 0 0 1 q2 q4 q0 q1 q3 1 1 29 Teorema 36 Seja L um conjunto aceito por um AFND Então existe um autômato finito determinístico AFD que aceita L Prova informal por construção Sejam A Q å d q0 F AFND A Q å d q0 F AFD tal que A é equivalente a A Como construir A a partir A 1 Cada elemento de Q será representado por q1q2 qi onde q1 q2 qi Î Q 2 q0 q0 3 Q 2Q com a notação do passo anterior 4 F conjunto formado pelos estados de Q que possuem pelo menos um estado em F 5 dq1q2qi a r1 r2rj Û dq1 a È dq2 a È È dqi a r1 r2 rj Exemplo Seja A q0q1 01 d q0 q1 com d dada por OBS Transições de estado nãoespecificadas no AFND devem levar ao estado f o qual terá no AFD equivalente o significado de um estado de erro ie um estado que se atingido durante o processamento de alguma cadeia de entrada significará seu não reconhecimento No exemplo acima dq10 f df 0 f df 1 f 0 0 01 1 1 01 q0 q1 f 30 Determinar A equivalente a A ie ambos devem reconhecer a mesma linguagem AQ 01 q0 F d 2Q f q0 q1 q1 q0 è Q f q0 q1 q0q1 q0 q0 F q1 q0q1 d f 0 f è d f 0 f d f 1 f è d f 1 f d q0 0 q0 q1 è d q0 0 q0q1 d q0 1 q1 è d q0 1 q1 d q1 0 f è d q1 0 f d q1 1 q0 q1 è d q1 1 q0q1 E ainda dq0 0 È dq1 0 q0 q1 è d q0q1 0 q0q1 q0q1 È f dq0 1 È dq11 q0 q1 è d q0q1 1 q0q1 q1 È q0 q1 OBS A B È f A B A B È f A B f LA LA 1 11x 0x x Î å L Amín 1 1101 001 01 AFD A º AFND A 01 0 0 1 1 01 q1 f q0 q0q1 0 1 1 0 D C A B 01 31 Teorema 37 Seja G uma gramática regular Þ um AFD A LG LA Teorema 38 Seja A um AFD Þ uma gramática regular G LG LA Exercício Seja A q0q1q2 ab d q0 q2 um autômato finito nãodeterminístico onde d é dada por d a b q0 q0q1 f q1 f q0q1q2 q2 f f 1a Desenhe o diagrama de transição de estados e determine LA 1b Construa o autômato finito determinístico mínimo equivalente a A 32 35 AUTÔMATO FINITO NÃODETERMINÍSTICO COM eMOVIMENTO Um AFNDe é uma 5tupla M S Q d q0 F com d da forma d Q S È e 2Q d q1 e q1 q2 qk ó Ao processar e o autômato assume simultaneamente o estado de origem q1 e todos os estados de destino q1 q2 qk Ou seja mesmo sem ler nada na fita de entrada num determinado momento ele é capaz de mudar de estado Exemplo M ab q0 qf d q0 qf d q0 e q0 qf ó Ao processar e o autômato assume simultaneamente o estado inicial q0 e o estado final qf L M aeb º ab Teorema 39 Para todo AFNDe é possível construir um AFND equivalente Blauth 2001 L aebea º aba b a q0 qf e a b a q0 q1 q2 e e AFNDe ab a q0 q1 q2 a b ab ab AFND 33 Teorema 310 Seja r uma expressão regular e Lr a linguagem representada por r Então existe um AFNDe A tal que LA Lr A prova do teorema Blauth 2001 Hopcroft Ullman 1979 é construtiva permitindo construir o AFNDe diretamente a partir de r OBS1 A capacidade de fazer o emovimento não se traduz em maior poder computacional já que os AFNDe continuam reconhecendo apenas linguagens regulares OBS2 No Hopcroft Ullman a partir de r 01 1 mostrase como construir diretamente um AFNDe que reconhece Lr Teorema 311 Obtenção de uma Gramática Regular Linear Unitária a partir de um Autômato Finito Determinístico ou NãoDeterminístico correspondente Executamse os 4 passos abaixo apesar de que produções desnecessárias poderão ser geradas 1 Cada estado do autômato dá origem a um símbolo nãoterminal da gramática 2 O estado inicial do autômato dá origem ao nãoterminal inicial da gramática 3 Transições para estados finais e nãofinais no autômato dão origem na gramática a regras de produção do tipo A s B A B Î N s Î å 4 Transições para estados finais no autômato dão origem na gramática a regras de produção do tipo A s s Î å Exemplo G å N S P Þ 1 q0 dá origem ao nãoterminal inicial S 2 q1 dá origem ao nãoterminal A 3 S 0S 1A A 0A 1S 4 S 1 A 0 0 0 q1 q0 1 1 34 Teorema 312 Obtenção de um Autômato Finito NãoDeterminístico a partir de uma Gramática Regular correspondente São os passos inversos do Teorema anterior 311 apenas observandose que uma regra de produção do tipo B e B nãoterminal dará origem a uma transição de estado com a cadeia vazia ie um AFNDe será obtido Exemplo Seja r 101 A partir de r construir G que gera Lr e daí construir um AFND que reconhece Lr Apresentamse 2 soluções obtidas a partir das gramáticas G1 N S P1 S e G2 N S P2 S tais que N S B S Símbolo nãoterminal inicial S 0 1 P1 e P2 Conjuntos de regras de produção Autômato finito determinístico equivalente aos AFNDs acima P1 S 1 S 0B B e B 1B 1 0 1 S B F e LG1 r1 101 P2 S 0 S 1 S 0B B 1B B 1 1 01 0 1 S B F LG2 r2 01011 0101 1001 101001 101 LG1 1 01 1 S B D 0 01 0 A P S 0A 1D 0 1 A 1A 1 0B D 0B 1B B 0B 1B Removendo B e D pois não há como trocálos por símbolos terminais B 0 1 e P S 0A 0 1 A 1A 1 35 Notação Transição no autômato finito q ax q x Û dq a q Com essa notação podese escrever LA x Î å q0 x q e q Î F Seja a gramática G S B 01 P S com P S 0B B 0B B 1S B 0 e o AFND correspondente construído a partir do procedimento anterior Assim podese representar os processos de geração e de reconhecimento da cadeia 00100 respectivamente como S Þ 0B Þ 00B Þ 001S Þ 0010B Þ 00100 Na geração S 00100 B 0100 B 100 S 00 B 0 F e No reconhecimento OBSERVAÇÕES 1 Além do Teorema de MyhillNerode há um outro teorema importante para ajudar a provar que uma determinada linguagem não é regular Tratase do chamado Pumping Lemma ou Teorema do Bombeamento Com ele podese provar por exemplo que a linguagem L abaixo não é regular L 0n1n n ³ 1 2 Os conjuntos regulares apresentam várias propriedades interessantes Por exemplo Se X e Y são conjuntos regulares Þ X È Y também é regular A classe das linguagens regulares é fechada sob a complementação isto é se L é regular sobre S então a linguagem SL também é regular 3 As linguagens regulares e os autômatos finitos são bem comportados no contexto de problemas de decisão ou seja tipicamente existem algoritmos para várias questões que envolvem os autômatos finitos e as linguagens regulares Por exemplo Se X e Y são linguagens regulares X Í Y ou X º Y são decidíveis Se A1 e A2 são autômatos finitos A1 º A2 é decidível 0 0 1 0 S B F 36 36 VARIANTES DE AUTÔMATOS FINITOS Autômatos Finitos com saída Máquina de Moore Máquina de Meally Def 315 Máquina de Moore Constituise de uma 6upla Q S D d l q0 onde D Alfabeto de saída D ³ 2 l Q D Função de saída a saída se define exclusivamente a partir do estado da máquina Exemplo O que faz esta máquina Dado um número natural que lhe é fornecido em representação binária ela calcula o resto da divisão inteira desse número por 3 ie ela implementa a operação MOD3 sobre o número Exemplo In 0 1 0 1 01012 510 Mod5 3 Out 0 Def 316 Máquina de Meally Também constituise de uma 6upla Q S D d l q0 mas a função l tem agora uma caracterização mais refinada l Q S D Função de saída a saída se define não só a partir do estado da máquina mas também em função do símbolo lido na fita Exemplo In 1 0 1 1 Out O que faz esta máquina Ela reconhece a linguagem representada por 010011 OBS O AFDmín requer 5 estados 0 0 0 1 1 1 1 0 2 q0 q2 q1 D 0 1 2 q1 0n 1n 1n 0n 1y 0y q0 q2 D n y 37 37 Autômatos Finitos como Formalismo de Modelagem de Sistemas Exemplo 1 P B Menezes Neste exemplo uma Máquina de Mealy trata algumas situações típicas de um diálogo que cria e atualiza arquivos A seguinte simbologia é adotada no grafo da função de transição áñ Entrada fornecida pelo usuário em um teclado por exemplo Saída gerada pelo programa em um vídeo por exemplo Ação interna ao programa sem comunicação com o usuário Resultado de uma ação interna ao programa é usado como entrada no grafo 38 Exemplo 2 Hopcroft Ullman duas canaletas verticais interligadas e três desvios Uma cadeia binária representa uma seqüência de bolas que entrarão no sistema mecânico abaixo onde A B Entradas das bolas C D Saídas das bolas X1 X2 X3 Desvios que mudam de posição a cada bola que passa por elas Bola em A 0 Bola em B 1 Questão que deve ser respondida Assumindo as alavancas na posição inicial em que se encontram no desenho quais são as cadeias binárias de entrada tais que a última bola sempre saia pela saída D A Máquina de Mealy a seguir modela o mecanismo representando os 8 estados possíveis do conjunto de 3 alavancas Em cada estado os símbolos ou afixados aos identificadores das alavancas indicam o posicionamento de cada alavanca 0C 0C 0C 0C 0C 0D 0D 0D 1C 1C 1D 1D 1D 1D 1D 1D 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 D C B A X1 X2 X3 39 AUTÔMATO FINITO E VARIAÇÕES QUADRO RESUMO AFD AFB bidirecional 1pebble AFB AFBND AFBND com endmarkers AFD com saída explícita Q S D d l q0 D alfabeto de saída Máquina de Mealy l QSD Máquina de Moore l QD Máquina de Turing unidirecional AFND nãodeterminístico AFNDe com emovimento Ë x1 x2 xn t0 tf 40 UNIDADE 4 MÁQUINAS COM PILHA Recordação Uma gramática livre de contexto GLC é uma 4upla G N Σ P S onde N Conjunto de símbolos nãoterminais Σ Alfabeto símbolos terminais N Ç Σ Æ V N È Σ S Símbolo não termina inicial S N P Conjunto de produções da forma A a A Î N a ÎV Exemplo de GLC representada na BNF BackusNaur Form G N Σ P S N S op var cte Σ 1 0 x y z P S var I cte I S op S I S op I var x I y I z cte 0 I 1 I 0 cte I 1 cte x 101y LG Î Ì 41 41 AUTÔMATOS DE EMPILHAMENTO Pushdown Automata PDA Linguagem Livres de Contexto são reconhecidas pelos PDAs Intuitivamente Dependendo do Estado do controle finito Símbolo que está sendo lido na fita de entrada Símbolo no topo da pilha o autômato de empilhamento Muda de estado Escreve um número finito de símbolos na pilha escrever e corresponde a apagar o símbolo no topo e Move sua cabeça leitora uma posição para a direita O autômato de empilhamento pode também efetuar emovimentos movimentos com a cadeia vazia que corresponde a mudar de estado e mudar o conteúdo da pilha sem ler o símbolo na fita de entrada isto é sem mover sua cabeça leitora para a direita 42 Definição 41 Um autômato de empilhamento é uma 7upla A Q Σ Γ δ q0 z0 F onde Q Conjunto finito não vazio de estados Σ Alfabeto de entrada Г Alfabeto da pilha q0 Î Q Estado inicial z0 Î Г Símbolo inicial da pilha F Q Conjunto de estados finais δ Q Σ È e Г È e 2Q Г não determinístico OBS Ou seja PDAs são nãodeterminísticos e já adiantando possuem poder computacional maior que a versão determinística PDAD Í Irrestrita Tipo 0 Recursivamente Enumerável Turing reconhecível Sensível ao Contexto Tipo1 Livre de Contexto Tipo2 Linguagens Recursivas Linguagens Decidíveis Livre de Contexto Determinísticas Regular Tipo3 43 Definição 42 Uma configuração de um PDA é um elemento de Q Σ Г Definição 43 Uma transição do autômato de empilhamento é representada por q ax zw q x yw q y δ q a z com q q Î Q a Î Σ e x Î Σ w y Î Г z Î Г OBS A condição z Î Г impõe que o PDA não faz transição se sua pilha estiver vazia Definição 44 A linguagem aceita por A Q Σ Г δ q0 z0 F por estado final é LA w Î Σ q0 w z0 q e x q Î F x Î Г Definição 45 A linguagem aceita por A Q Σ Г δ q0 z0 F por pilha vazia é NA w Î Σ q0 w z0 q e e q Î Q OBS LA NA Definição 47 Seja Σ um alfabeto e A um autômato de empilhamento LΣ L Σ L LA Conjunto das linguagens aceitas por estado final NΣ L Σ L NA Conjunto das linguagens aceitas por pilha vazia Proposição 41 LΣ NΣ L LA L NB Lema 41 Se L LA para algum autômato de empilhamento A então existe autômato de empilhamento B tal que L NB Proposição 42 LΣ NΣ L Σ L é linguagem livre de contexto Û Î È Í Í Þ Í 44 Exemplo Construir autômato de empilhamento que aceita L 0n1n n 0 A q0 q1 q2 01 z 0 δ q0 z q0 onde δ é dado por δ q0 0 z q1 0 Empilha 0s δ q1 0 0 q1 0 δ q1 1 0 q2 e Para cada 1 encontrado desempilha um 0 δ q2 1 0 q2 e δ q2 e z q0 z Podese provar que a linguagem 0n1n n 0 é livre de contexto determinística O autômato A do exemplo acima reconhecedor da linguagem 0n1n n0 é determinístico e z z 1 0 e q0 q1 q2 0 z 0 0 0 0 1 0 e 45 Definição 46 Um autômato de empilhamento A Q Σ Г δ q0 z0 F é determinístico se para todo q a z Î Q Σ Г temse 1 δ q a z 1 2 Apenas 1 das configurações a seguir é válida ou seja é δq a z δq ε z δq a ε δq ε ε OBS Diferentemente dos AFDs PDADs admitem εmovimentos sobre a fita ou seja δ ε já que sua configuração também envolve a pilha Há ainda εmovimentos na pilha ie δ ε A condição 1 estabelece que cada transição leva a no máximo 1 configuração A condição 2 estabelece que isso deve ocorrer mesmo quando εmovimentos são possíveis na fita e na pilha Ou seja δq a z e δq ε z seria um movimento ignorando a fita δq a z e δq a ε seria um movimento ignorando a pilha δq a z e δq ε ε seria um movimento ignorando a fita e a pilha 46 Um exemplo de como intuir que a computabilidade dos PDAs possa ser maior que a dos PDADs Considerese a linguagem L wwR w Î 01 wR é o reverso de w ou seja L é formada por palíndromes pares Intuitivamente um autômato de empilhamento para reconhecer L deverá ser não determinístico porque durante o processamento de uma cadeia wwR não há maneira de saber quando termina a cadeia w e começa a cadeia wR Assim para cada símbolo lido o autômato deve prever duas possíveis situações a cadeia w ainda não terminou a cadeia w terminou e os próximos símbolos serão de wR Para a linguagem L wawR wÎ01 Σ0 1 a podese construir um PDAD que a reconhece No entanto não é possível construir um PDAD para reconhecer L para isso é necessário um PDA pois L é livre de contexto mas não lc determinística OBS Replicações de um PDA que reconhece a linguagem L de palíndromes pares ao processar a cadeia 001100 M0 0 M0 0 M1E M1D 1 M2E M2D M1D 1 M3E M3D M2D M1D 0 M4E M4D M3D M2D M1D 0 M5E M5D M4D M3D M2D M1D Exercício Podese provar que a linguagem aibjck i j k 0 com i j or i k é livre de contexto mas não é livre de contexto determinística Construir um PDA que reconhece L 47 Exemplo Hopcroft Motwani e Ullman 3rd ed 2007 p230 PDA que reconhece a linguagem de palíndromes binárias pares L wwR wÎ01 wR é o reverso de w A notação empregada no exemplo para as transições de estado é mais compacta do que a que definimos ab b Þ lendo o símbolo a na fita e b na pilha a pilha não se altera ab Xb Þ lendo o símbolo a na fita e b na pilha adicione a cadeia X à pilha Ou seja cada uma das transições de estado acima corresponde na nossa notação a duas transições ab b Þ ab ε Þ ab b ab Xb Þ ab ε Þ ab Xb Configuração inicial q0 0 Z0 Sequência de transições que levam à aceitação da cadeia de entrada 0 1 1 0 mas há transições alternativas que não levariam ao reconhecimento q0 0 Z0 Þ q0 0 Z0 Pilha 0 Z0 q0 1 0 Þ q0 1 0 Pilha 1 0 Z0 Neste ponto ocorre um εmovimento para o estado q1 q0 ε 1 Þ q1 1 Pilha 1 0 Z0 q1 1 1 Þ q1 ε Pilha 0 Z0 q1 0 0 Þ q1 ε Pilha Z0 Neste ponto ocorre um εmovimento para o estado q2 q1 ε Z0 Þ q2 Z0 Pilha Z0 48 Definição 48 Derivações em gramáticas livres de contexto Gramática de balanceamento de parênteses Gbp NS Σ S Pbp com Pbp S SS S 1 Derivações MaisàEsquerda leftmost derivations S Þlm SS Þlm SS Þlm S Þlm 2 Derivações MaisàDireita rightmost derivations S Þrm SS Þrm S Þrm S Þrm 3 Derivações arbitrárias S Þ SS Þ SSS Þ SS Þ S Þ S Þ SS Þ SSS Þ SS Þ S Þ Não são derivações maisàdireita nem maisàesquerda Definição 49 Gramática Ambígua Uma gramática livre de contexto é ambígua se alguma das cadeias geradas a partir dela possuir mais de uma derivação maisàesquerda ou maisàdireita o que acaba gerando mais de uma árvore sintática parsing tree associada OBS 1 O fato de Gbp ter duas derivações diferentes para a cadeia não garante que é Gbp ambígua pois essas derivações não são maisàesquerda 2 A multiplicidade de derivações maisàesquerda tem uma certa maior importância pois escrevemos e lemos código computacional a partir da esquerda 3 Não existe e nunca existirá um algoritmo para determinar se uma gramática livre de contexto arbitrária é ambígua ou não Exemplo 1 A gramática livre de contexto de somas e subtrações A A A A A a é ambígua pois a cadeia a a a possui 2 derivações maisàesquerda A Þ A A A Þ A A Þ a A Þ A A A Þ a A A Þ a A A Þ a a A Þ a a A Þ a a a Þ a a a 49 Ou a cadeia a a a possui 2 árvores sintáticas A A A A A a Exemplo 2 O problema do else pendurado dangling else Numa gramática contendo as regras Comando If Condição then Comando If Condição then Comando else Comando Condição A cadeia expressão If a then If b then s1 else s2 é ambígua tem duas interpretações sintáticas possíveis dependendo se o else é associado ao primeiro ou ao segundo If If a then begin If b then s1 end else s2 If a then begin If b then s1 else s2 end Exercício Mostre que a gramática G S A 0 1 S P geradora da linguagem L 00 01 10 11 é não ambígua P S A A A 0 1 Definição 410 Linguagem Inerentemente Ambígua Uma linguagem livre de contexto é inerentemente ambígua se todas as gramáticas livres de contexto geradoras desta linguagem são ambíguas 50 Análise Sintática Descendente com Retorno Seja a gramática G livre de contexto definida com å a N E T F S E P E ET T T TF F F a E Eis um PDA que reconhece sua linguagem correspondente por pilha vazia PDAG q å Γ δ q E com å a Γ å È E T F e δ dado por δq ε E q ET q T 1a 1b δq ε T q TF q F 2a 2b δq ε F q a q E 3a 3b δq x x q ε x Î å 4 Notação usada δ topo da pilha cadeia que substituirá o topo da pilha δ x Y º δ x ε Þ δ Y A cadeia aaa pode ser reconhecida com a seguinte sequência de transições q aaa E 1a q aaa ET OBS O topo da pilha é E 1b q aaa TT 2b q aaa FT 3a q aaa aT 4 q aaa T 4 q aaa T 2a q aaa TF 2b q aaa FF 3a q aaa aF 4 q aaa F 4 q aaa F 3a q aaa a 4 q aaaε ε 51 Observando as transições do PDAG notase que a fita de entrada contém a cada instante a parte da cadeia de entrada que falta ser analisada e que o conteúdo da pilha simula uma derivação mais à esquerda E Þ ET Þ TT Þ FT Þ aT Þ aTF Þ aFF Þ aaF Þ aaa Este autômato de pilha é conhecido como Reconhecedor Descendente ou Analisador Sintático Descendente topdown parser porque como simula derivações mais à esquerda constrói a árvore sintática da cadeia de entrada de cima para baixo e da esquerda para a direita que no exemplo corresponde a E E T T T F F F a a a Entretanto como pode ser observado da definição da função de transição de estados δ o autômato PDAG é nãodeterminístico sendo que as transições mostradas foram convenientemente escolhidas a cada passo Uma questão interessante é Seria possível automatizar este processo A resposta é sim através de um algoritmo que implementa o processo conhecido como Análise Sintática Descendente com Retorno topdown backtrack parsing a qual é descrita pelos 4 passos a seguir 1 Começar a árvore sintática pelo símbolo inicial da pilha o símbolo inicial da gramática Esse símbolo é o nó ativo inicial Em seguida executar os passos 2 e 3 recursivamente 2 Se o nó ativo é um nãoterminal A escolher a primeira Aprodução ainda não utilizada A X1X2Xk e criar na árvore sintática X1 X2 Xk como descendentes diretos de A Marcar o primeiro destes descendentes o mais à esquerda como ativo 3 Se o nó ativo é um terminal a então comparálo com o símbolo atual de entrada Se eles foram iguais então tornar ativo o símbolo imediatamente à direita de a na árvore e avançar com a cabeça leitora para o próximo símbolo de entrada Se eles forem diferentes retornar ao último não terminal A expandido para o qual existe uma Aprodução ainda não utilizada 4 Se não existe nó ativo e todos os símbolos de entrada foram lidos então a análise sintática termina com sucesso a cadeia foi reconhecida Caso contrário rejeitar a cadeia isto é existe um erro sintático na cadela 52 Exemplo Seja a gramática G åa b c NS S P S aSbS aS c com a cadeia de entrada aacbc 53 OBS Exemplos de linguagens que não são livres de contexto 1 L1 ww w Î a b G1 S A B C D E a b P S P S ABC AB aAD AB bAE DC BaC EC BbC Da aD Db bD Ea aE Eb bE AB e C e aB Ba bB Bb 2 L2 w Î a b c a b c G2 S A B C a b c P S P S ABC S ABCS AB BA AC CA BC CB BA AB CA AC CB BC A a B b C c 3 L3 0n1n2n n 0 4 L4 ap p é um número primo 54 OBS 1 Como saber se uma dada linguagem L é de determinado tipo Não há solução geral nem mesmo quando a pergunta é L é regular Teoremas ajudam a determinar se L não é de determinado tipo Teorema de MyhillNerode Pumping lemma para linguagens regulares Pumping lemma para linguagens livre de contexto etc OBS 2 Como saber se uma dada gramática G é de determinado tipo É útil reescrever as regras de produção de G de forma que as novas regras sigam formas normais conhecidas Ex Palíndromes pares de as de bs L wwR w Î a b P1GL S e É uma GLC mas poderseia pensar S a b que ela é RE estrita pois não está de S aSa bSb acordo com a formal normal das GSC com S e S não poderia aparecer do lado direito de regras Reescrevendo as produções para corrigir assumindo que o nãoterminal L passa a ser o novo nãoterminal inicial P2GL L e L S Agora OK S a b aSa bSb Outras formas normais existem a Î S S X Y Z Î N W Î N Chomsky X a X YZ S e Greibach X a X aW S e 55 42 AUTÔMATO DE EMPILHAMENTO E VARIAÇÕES PDA Û LLC nãodeterminístico PDAB Aceita linguagens que não são livres de contexto PDADB Aceita linguagens que são reconhecidas em tempo linear por um computador por ex Lanbncn n 1 ³ PDA com escrita na fita Tornase um Pushdown Transducer PDA com 2 pilhas Equivalente a uma Máquina de Turing LLCD PDAD determinístico Û 56 LINGUAGENS L wwR wÎ01 wR é o reverso de w Lanbncn n 1 L wawR wÎ01 OBS LLk e LRk são apropriadas para análise sintática sem retorno sem backtracking ³ Linguagem Recursivamente Enumerável Linguagem Recursiva Linguagem Sensível ao Contexto Linguagem Livre de Contexto Linguagem Livre de Contexto Determinística LRk Linguagem Regular 57 43 STACK AUTOMATA Autômatos de Pilha PDA 1 Cabeça bidirecional 2 Fita com endmarkers 3 Modo adicional de deslocamento na pilha apenasleitura ao longo de toda a sua extensão uma vez neste modo ele só termina quando a cabeça da pilha voltar ao topo Aceitação por estado final No início Cabeça de entrada está na extremidade à esquerda da fita Controle está em q0 Pilha tem um único símbolo Г0 definido como de início do processo 58 DSA NSA NEDSA NENSA 1NSA 1NENSA 1NEDSA 1DSA unidirecional movimento para a direita nonerasing só empilha nunca desempilha 1DSA 1NENSA 1NSA CFL 1NEDSA DCFL LRk 59 1DSA 1NENSA 1NSA CFL 1NEDSA DCFL LRk LLk DSA DTIME𝑛 NEDSA DSPACEn logn DSPACEn CSL NSPACEn Indexed Languages 0Llanguages NENSA NSPACEn2 NSA DTIME2 60 44 DETERMINISTIC AUXILIARY PDA DAPDA Aceita w somente por pilha vazia Sn DAPDA Sn NDAPDA LsnDAPDA Linguagens aceitas por uma MT em tempo exponencial ie são do tipo cSn onde c é uma constante PDA 1 Cabeça bidirecional na fita de entrada 2 Fita de entrada com endmarkers 3 Fita auxiliar finita tamanho Sn para leitura e escrita e movimento bidirecional 45 AUTOMATO LIMITADO LINEARMENTE Linear Bounded Automata wo Cadeia de entrada Cabeca de leitura 3k in yry iex naodeterministico cabeca de escrita lettura 1 3 y2 caracteres ao final oo HHesiCtSCé da Cotta e Equivale a uma Maquina de Turing naodeterministica com fita limitada e Linguagens sensiveis ao contexto Recursivas reconhecimento ou nao de uma cadeia sempre para 2 ALLDet ALL Naodet 61