Baixe o app para aproveitar ainda mais
Prévia do material em texto
Capítulo 0 Teoria da Complexidade: Classificar os problemas em fáceis e difíceis. Teoria da Computabilidade: Classificar os problemas em solúveis ou não. Conjunto: É um grupo de objetos representados como uma unidade. Podem conter qualquer tipo de objeto e até mesmo outros conjuntos. ● 7 ∈ {7,21,57} = 7 pertence ao conjunto. ● 8 ∉ {7,21,57} = 8 não pertence ao conjunto. ● A ⊆ B = A é subconjunto de B se todos os elementos de A pertencerem a B. ● A ⊊ B = A é subconjunto próprio de B se A é subconjunto de B e não é igual a B. ● Ø = Conjunto vazio. ● AUB = Combinação de todos elementos de A e B em um único conjunto. ● A∩B = Conjunto de elementos presentes em A e B. ● AxB = Produto Cartesiano ou Produto Cruzado = Conjunto de todos os pares onde o primeiro elemento é membro de A e o segundo é membro de B. Elementos / Membros: São os objetos em um conjunto. Multiconjunto: Levase em consideração o número de ocorrências dos membros. Em um conjunto, o número de ocorrências não muda o conjunto. Sequência: É uma lista de objetos na mesma ordem. Em um conjunto, a ordem não importa, mas na sequência sim. Usualmente, se escreve entre parênteses. ● (7,21,57) ≠ (21,7,57) ● {7,21,57} = {7,7,7,21,57} Uplas: São sequências finitas. Uma sequência com k elementos é uma kupla. Então (7,21,57) é uma 3upla. Uma 2upla também é chamada de par. Conjunto das Partes: O conjunto das partes de A é o conjunto de todos os subconjuntos de A. Se A = {0,1}, o conjunto das partes de A = {Ø, {0}, {1}, {0,1}}. O conjunto com todos os pares cujos elementos são 0s e 1s = {(0,0), (0,1), (1,0), (1,1)}. Função / Mapeamento: Um objeto que estabelece uma relação entradasaída. Também é chamada de mapeamento. Se �(a) = b, dizemos que � mapeia a para b. ● Domínio = Conjunto das possíveis entradas. ● Contradomínio = Conjunto das saídas ● �: D⟶C = � é uma função com domínio D e contradomínio C ● add: ƶ x ƶ ⟶ ƶ ○ add(2,2) = 4 ● Uma função que usa todos os elementos do contradomínio é dita ser sobre o contradomínio. ● Uma função com k argumentos é chamada função kária, e k é a aridade da função. Para k = 1, função unária; k = 2, função binária. ● Notação infixa, o símbolo da função fica entre os argumentos: a + b. ● Notação prefixa, o símbolo da função precede os argumentos: adi(a,b). Propriedade / Predicado: Função cujo contradomínio é {Verdadeiro,Falso}. Relação de Equivalência: É um tipo especial de relação binária que captura a noção de 2 objetos sendo iguais em algum aspecto. Uma relação binária R só é de equivalência se: 1. R é reflexiva para todo x, xRx; 2. R é simétrica para todo x e y, xRy implica yRx 3. R é transitiva para todo x, y, z, zRy e yRz implica xRz. Grafos: É um conjunto de pontos com linhas ligando alguns dos pontos. ● Se V é o conjunto de nós de G e E é o conjunto de arestas, G = (V,E). Nós / Vértices: São os pontos. Arestas: São as linhas. Grau do nó: É o número de arestas em um nó. Entre dois nós só é permitido no máximo uma aresta. O par (i,j) representa a aresta que conecta i e j. (i,j) e (j,i) são a mesma coisa. Subgrafo: G é um subgrafo de do grafo H se os nós de G formam um subconjunto dos nós de H juntamente com as arestas correspondentes. Caminho: É uma seqüência de nós conectados por arestas. Caminho simples: Um caminho que não repete nenhum nó. Caminho direcionado: Todas as setas apontam na mesma direção que seus passos. Um grafo direcionado é fortemente conexo se um caminho direcionado conecta cada dois nós. Grafo Conexo: Cada dois nós têm um caminho entre eles. Ciclo: Caminho que começa e termina no mesmo nó. ● Ciclo Simples: ○ Possui pelo menos 3 nós e repete somente o primeiro e o último nós. Grafo direcionado: Se possui setas ao invés de linhas. O número de setas apontando a partir de um dado nós é o grau de saída desse nó. O número de setas apontando para o nó é o grau de entrada. Árvore: Um grafo é uma árvore se ele é conexo e não tem ciclos simples. Raiz: Nós de grau 1 em uma árvore, exceto a raiz, são as folhas. Cadeias e Linguagens: Cadeias de caracteres são blocos básicos fundamentais em ciência da computação. Alfabeto: É qualquer conjunto finito nãovazio. Símbolos: São membros do alfabeto. Cadeia sobre um alfabeto: É uma sequência finita de símbolos daquele alfabeto. Por exemplo, Se ∑1= {0,1}, então 01001 é uma cadeia sobre ∑1. ∑* = conjunto de todas as cadeias sobre ∑, incluindo ε. Linguagem: É um conjunto de cadeias sobre um alfabeto. ● L(M) = A: A é a Linguagem da máquina M/ M reconhece A. Comprimento: Se w é uma cadeia sobre ∑2, o comprimento de w, “|w|”, é o número de símbolos que ele contém. Cadeia de comprimento zero é chamada cadeia vazia e é escrita “ε”. Reverso: É a cadeia obtida escrevendo w na ordem inversa (i.e., wn, wn1, …, w1). Subcadeia: z é subcadeia de w se z aparece consecutivamente dentro de w. Por exemplo, lele é uma subcadeia de paralelepipedo. Concatenação: Temos a cadeia x de comprimento m e a cadeia y de comprimento n. A concatenação seria: x1...xmy1...yn. Uma concatenação de uma cadeia com si própria várias vezes é denotada com expoente, xˆk = xxxx... (k vezes). Ordenação Lexicográfica: a ordenação de todas as cadeias sobre o alfabeto {0,1} é (ε, 0, 1, 00, 01, 11, 000, …). P(∑*) = Conjunto de todas as linguagens sobre um alfabeto ∑. Lógica Booleana ● Conjunção (e) = ∩ ● Disjunção (ou) = U ● Operandos: P∩Q, P e Q são operandos da operação. ● XOR = ⊕ ● Igualdade = ↔ ● Implicação = → ● P ∨ Q = ¬(¬P ∧ ¬Q) ● P → Q = ¬P ∨ Q ● P ↔ Q = (P → Q) ∧ (Q → P ) ● P ⊕ Q = ¬(P ↔ Q) Lei distributiva: P ∧(Q∨R) = (P ∧Q)∨(P ∧R) Definições, Teoremas e Provas Uma prova bem escrita é uma seqüência de enunciados. Definições: Descrevem os objetos e noções que usamos. Precisão na definição é essencial, deixando claro o que constitui um objeto e o que não o constitui ao definílo. Enunciados Matemáticos: Expressa que algum objeto tem uma certa propriedade. Pode ou não ser verdadeiro, mas deve ser preciso, sem haver ambiguidade sobre seu significado. Prova: É um argumento lógico convincente de que o enunciado é verdadeiro. Um matemático requer prova além de qualquer dúvida. Teorema: É um enunciado matemático demonstrado verdadeiro. Lema: Enunciados que provamos que são interessantes somente por ajudar na prova de um outro enunciado mais significativo. Corolário: Enunciado deduzido a partir de um outra (anteriormente) demonstrada, fazendo com que um conhecimento seja acrescentado a mesma. Capítulo 1 1.1 Autômatos Finitos ● Estado Inicial: Indicado pela seta que aponta a partir do nada. ● Estado de Aceitação: Duplo círculo. ● Transições: Setas saindo de um estado para outro. ● Saída Aceita: Se ao ler o último símbolo, o autômato está no estado de aceitação. ● Saída Rejeita: Se não está no estado de aceitação. ● Função de Transição (δ): Define as regras de movimentação. ○ ઠ(x,1) = y : Se o autômato está em x quando lê 1, ele vai para y. Definição Formal de AFD: É uma 5upla (Conjunto de estados, alfabeto de entrada, regras para movimentação, estado inicial e estados de aceitação; (Q,∑,δ,q0,F)) onde: ● Q = o conjunto finito conhecido como os estados; ● ∑ = conjunto finito chamado de alfabeto; ● δ : Q x ∑ → Q = função de transição; ● q0 ∈ Q = estado inicial; ● F ⊆ Q = conjunto de estados de aceitação; Um autômato pode reconhecer várias cadeias, mas sempre reconhece somenteuma linguagem. Mesmo não aceitando cadeia nenhuma, ela vai reconhecer a linguagem vazia Ø. Definição Formal de Computação: Se M = (Q,∑,δ,q0,F)), suponha que w = w1w2w3...wn seja uma cadeia onde cada wi é membro do alfabeto ∑. M aceita w se existe uma seqüência de estados r0, r1, …, rn em Q com 3 condições: 1. r0 = q0 ➢ A máquina começa no estado inicial. 2. δ(ri, wi+1) = ri+1 para i = 0, …, n1 ➢ A máquina vai de estado para estado conforme a função de transição. 3. rn ∈ F ➢ A máquina aceita sua entrada se ela termina num estado de aceitação. Linguagem Regular: Se algum automato finito a reconhece, a linguagem é regular. Dizemos que M reconhece a linguagem A se A = {w | w M aceita w}. Operações Regulares: Sejam A e B linguagens, as operaões regulares são ● União: AUB = {x | x ∈ A ou x ∈ B} ● Concatenação: A ० B = {xy | x ∈ A e y ∈ B} ● Estrela: A* = {x1x2...xk | k � 0 e cada xi ∈ A} Como exemplo, suponha que o alfabeto ∑ seja o padrão 26 letras {a, b, c,…, z} e as linguagens são A = {legal, ruim} e B = {garoto, garota}. ● AUB = {legal, ruim, garoto, garota} ● A ० B = {legalgaroto, legalgarota, ruimgaroto, ruimgarota} ● A* = {ε, legal, ruim, legallegal, legalruim, ruimlegal, ruimruim, legallegallegal, legallegalruim, legalruimlegal, legalruimruim,...} Uma coleção de objetos é fechada sob alguma operação se, aplicando a operação, recebese um objeto ainda na coleção. Por exemplo, seja N = {1, 2, 3, …} o conjunto dos números naturais, N é fechado sob multiplicação pois para qualquer x e y em n, x☓y também está em N. O mesmo não o corre para divisão pois ½ não está em N, então N não é fechado sob divisão. A coleção de linguagens regulares é fechada sob as 3 operações regulares. Teorema 1.25 A classe de linguagens regulares é fechada sob a operação de união. Ou, se A1 e A2 são linguagens regulares, o mesmo acontece com A1UA2. Prova por construção: Construir um autômato M que reconheça A1UA2 a partir de M1 e M2 sabendo que M1 reconhece A1 e M2 reconhece A2. M funciona simulando M1 e M2 e aceita se uma das simulações aceita. Simular as duas ao mesmo tempo e guardar o estado em que cada máquina se encontra se ela tivesse lido até esse ponto da entrada. O número de estados possíveis se M1 tem k1 estados e M2 tem k2 estados é k1 x k2, que é o número de estados de M. Supomos que M1 =(Q1,∑,δ1,q1,F1)) reconhece A1 e M2 = (Q2,∑,δ2,q2,F2)) reconhece A2, a construção de M = (Q,∑,δ,q0,F)) se dará por: 1. Q = {(r1, r2) | r1 ∈ Q1 e r2 ∈ Q2} ○ É o produto cartesiano de todos os pares de estados. 2. ∑ é o mesmo para M1 e M2. E mesmo com alfabetos diferentes ∑1 e ∑2, o teorema permanece verdadeiro pois a prova seria modificada para tornar ∑ = ∑1 U ∑2. 3. δ((r1, r2), a) = (δ1(r1, a), δ2(r2, a)) para cada (r1, r2) ∈ Q e cada a ∈ ∑ 4. q0 = (q1,q2) 5. F = {(r1, r2) | r1 ∈ F1 ou r2 ∈ F2} ○ É o conjunto de pares onde um dos membros é o estado de aceitação de M1 ou M2. É o mesmo que dizer que F = (F1 x Q2) U (Q1 X F2) 1.2 Nãodeterminismo ● Determinismo: acontece quando a máquina está em um dado estado e lê o próximo símbolo de entrada e sabemos qual será o próximo estado. ● NãoDeterminismo: Várias escolhas podem existir para o próximo estado. É uma generalização de determinismo, ou seja, todo autômato determinístico é um autômato nãodeterminístico. AFD: Autômato Finito Determinístico ● Todo estado sempre tem exatamente uma seta de transição saindo para cada símbolo no alfabeto. AFN: Autômato Finito NãoDeterminístico ● Tem possibilidades de seguir caminhos diferentes com um mesmo símbolo no alfabeto para um estado dado. ● Dividese em cópias de si mesmo para seguir pelos possíveis caminhos em paralelo e “morre” se o próximo símbolo de entrada não aparece sobre qualquer seta que saia do estado atual. ● Se qualquer cópia estiver em um estado de aceitação ao final da entrada, o AFN aceita a cadeia. ● “ε”: Se um estado com um símbolo ε sobre uma seta saindo for encontrado, a maquina dividese em múltiplas cópias sem ler qualquer entrada, uma cada seguindo uma das setas saindo rotuladas com ε e uma permanece no estado corrente. Definição Formal de AFN: A diferença entre a definição de AFD e AFN é basicamente a função de transição. No AFD, a função de transição toma um estado e um símbolo de entrada e produz o próximo estado. No AFN, a função de transição toma um estado e um símbolo de entrada ou a cadeia vazia “ε” e produz um conjunto de próximos estados possíveis. Convencionamos que P(Q) é o conjunto das partes de Q, que é a coleção de todos os subconjuntos de Q. Para qualquer alfabeto ∑, escrevemos ∑ε como sendo ∑U{ε}. Então, um Autômato Finito NãoDeterminístico é uma 5upla (Conjunto de estados, alfabeto de entrada, regras para movimentação, estado inicial e estados de aceitação; (Q,∑,δ,q0,F)) onde: ● Q = um conjunto finito de estados; ● ∑ = alfabeto finito; ● δ : Q x ∑ε → P(Q) = função de transição; ● q0 ∈ Q = estado inicial; ● F ⊆ Q = conjunto de estados de aceitação; Definição Formal de Computação: Seja N = (Q,∑,δ,q0,F) um AFN e w seja uma cadeia do alfabeto ∑. N aceita w se w = w1w2w3...wn onde cada wi é membro do alfabeto ∑ε e existe uma seqüência de estados r0, r1, …, rn em Q com 3 condições: 4. r0 = q0 ➢ A máquina começa no estado inicial. 5. ri+1 ∈ δ(ri, wi+1), para i = 0, …, n1 ➢ O estado ri +1 é um dos próximos estados permissíveis quando N está em ri e lendo wi+1. 6. rn ∈ F ➢ A máquina aceita sua entrada se o último estado é de aceitação. Equivalência de AFNs e AFDs AFNs e AFDs reconhecem a mesma classe de linguagens e descrever um AFN para uma linguagem é muitas vezes mais fácil que descrever um AFD para a mesma linguagem. Dois autômatos são equivalentes se eles reconhecem a mesma linguagem. Teorema 1.39 Todo autômato finito nãodeterminístico tem um autômato finito determinísto equivalente. Prova: Se k é o número de estados do AFN, ele tem subconjuntos de estados, cada um2k correspondendo a uma das possibilidades que o AFD tem. Então esse AFD que simula o AFN terá estados.2k Seja N = (Q,∑,δ,q0,F) o AFN que reconhece alinguagem A, vamos construir o AFD M = (Q’,∑,δ’,q0’,F’) que também reconhece A. 1. Q’ = P(Q) ○ Todo estado de M é um conjunto de estados de N. 2. δ’(R,a) = δ(r,a), para R ∈ Q’ e a ∈ ∑∪ r∈R ○ Quando M lê símbolo “a” no estado R, ele mostra para onde a leva cada estado em R. Como cada estado pode ir para um conjunto de estados, temos que tomar a união de todos esses conjuntos. ○ δ(r,a) significa a união dos conjuntos δ(r,a) para cada r em R.∪ r∈R 3. q0’ = {q0} ○ M começa no estado correspondente à coleção contendo somente o estado inicial de N. 4. F’ = {R ∈ Q’ | R contém um estado de aceitaçãode N} ○ A máquina M aceita se um dos possíveis estados nos quais N poderia estar nesse ponto é um estado de aceitação. Essa prova foi construída no caso onde N não tem setas ε. Para a construção completa da prova considerando as setas ε, para qualquer estado R de M, definimos E(R) como a coleção de estados que podem ser atingidos a partir de R indo somente ao longo de setas ε, incluindo os membros de R. Então: E(R) = {q | q pode ser atingido a partir de cada elemento de R viajando ao longo de ou mais setas ε} Com isso, temos que modificar a função de transição de M para ser possível caminhar sobre as setas ε e atingir estados substituindo δ(r,a) por E(δ(r,a)): δ’(R,a) = {q ∈ Q| q ∈ E(δ(r,a)) para algum r ∈ R} Também teremos que mudar o estado inicial de M para que o autômato também possa caminhar para os estados possíveis a partir do estado inicial de N ao longo de setas ε. Desse modo, mudamos q0’ para E({q0}). Então temos: ● Q’ = P(Q) ● ∑ = alfabeto ● δ’(R,a) = {q ∈ Q| q ∈ E(δ(r,a)) para algum r ∈ R} ● q0’ = E({q0}) ● F’ = {R ∈ Q’ | R contém um estado de aceitação de N} Corolário 1.40 Uma linguagem é regular se e somente se algum AFN a reconhece. Minimização de AFDs 2 estados são equivalentes se, para qualquer entrada a partir desses estados, o resultado é o mesmo (aceita ou rejeita). ● 2 estados q e q’ são 0equivalentes se ambos são estados de aceitação ou ambos são estados de nãoaceitação. ● 2 estados q e q’ são 1equivalentes se δ(q, a) e δ(q’, a) são 0equivalentes para todo a ∈ ∑. ● 2 estados q e q’ são 2equivalentes se δ(q, a) e δ(q’, a) são 1equivalentes para todo a ∈ ∑. ● 2 estados q e q’ são nequivalentes se δ(q, a) e δ(q’, a) são (n1)equivalentes para todo a ∈ ∑. → Então 2 estados são equivalentes se são nequivalentes para todo n ≥ 0. Exemplo 1: 0Equivalentes: A = {q1, q2, q3, q4, q5, q6, q7, q8, q9} → aceitação B = {q10} → nãoaceitação q1 q2 q3 q4 q5 q6 q7 q8 q9 q10 a A A A A B B A A A B b A A A A A A A A B B 1Equivalentes: A = {q1, q2, q3, q4, q7, q8} B = {q5, q6} C = {q9} D = {q10} q1 q2 q3 q4 q7 q8 q5 q6 q9 q10 a A B A B A B D D A D b A A C A C A A A D D 2Equivalentes: A = {q1} B = {q2, q4, q8} C = {q3, q7} D = {q5, q6} E = {q9} F = {q10} q1 q2 q4 q8 q3 q7 q5 q6 q9 q10 a B D D D B B F F B F b C C C C E E C C F F 3Equivalentes: A = {q1} B = {q2, q4, q8} C = {q3, q7} D = {q5, q6} E = {q9} F = {q10} ● A tabela estabilizou nesse ponto, pois os 3equivalentes são iguais aos 2equivalentes. Com isso, podemos construir o AFD mínimo: A B C D E F a B D B F B F b C C E C F F Exemplo 2: q1 q2 q3 q4 q5 q6 q7 a q2 q3 q3 q1 q3 q5 q6 b q1 q4 q3 q7 q4 q7 q7 0Equivalentes: A = {q1} → aceitação B = {q2, q3, q4, q5, q6, q7} → nãoaceitação q1 q2 q3 q4 q5 q6 q7 a B B B A B B B b A B B B B B B 1Equivalentes: A = {q1} B = {q2, q3, q5, q6, q7} C = {q4} q1 q2 q3 q5 q6 q7 q4 a B B B B B B A b A C B B C B B 2Equivalentes: A = {q1} B = {q2, q6} C = {q3, q5, q7} D = {q4} q1 q2 q6 q3 q5 q7 q4 a B C C C C B A b A D C C D C C 3Equivalentes: A = {q1} B = {q2, q5} C = {q3, q6} D = {q4} E = {q7} q1 q2 q5 q3 q6 q4 q7 a B C C C B A C b A D D C E E E 4Equivalentes: A = {q1} B = {q2, q5} C = {q3} D = {q4} E = {q6} F = {q7} q1 q2 q5 q3 q4 q6 q7 a B C C C A B E b A D D C F F F ● A tabela estabilizou nesse ponto, pois os 4equivalentes são iguais aos 3equivalentes. Com isso, podemos construir o AFD mínimo: A B C D E F a B C C A B E b A D C F F F Exemplo 3: q1 q2 q3 q4 q5 q6 q7 q8 0 q2 q7 q1 q3 q8 q3 q7 q7 1 q6 q3 q3 q7 q6 q7 q5 q3 0Equivalentes: A = {q3} → aceitação B = {q1, q2, q4, q5, q6, q7, q8} → nãoaceitação q1 q2 q8 q4 q5 q6 q7 q3 0 B B B A B A B B 1 B A A B B B B A 1Equivalentes: A = {q1, q5, q7} B = {q2, q3, q8} C = {q4, q6} q1 q5 q7 q2 q3 q8 q4 q6 0 B B A A A A B B 1 C C A B B B A A 2Equivalentes: A = {q1, q5} B = {q2, q3, q8} C = {q4, q6} D = {q7} q1 q5 q2 q3 q8 q4 q6 q7 0 B B D A D B B D 1 C C B B B D D A 3Equivalentes: A = {q1, q5} B = {q2, q8} C = {q3} D = {q4, q6} E = {q7} q1 q5 q2 q8 q3 q4 q6 q7 0 B B E E A C C E 1 D D C C C E E A ● A tabela estabilizou nesse ponto, pois os 3equivalentes são iguais aos 2equivalentes. Com isso, podemos construir o AFD mínimo: A B C D E 0 B E A C E 1 D C C E A FECHO SOB AS OPERAÇÕES REGULARES Provar nãodeterministicamente as operações de união, concatenação e estrela. Teorema 1.45 A classe das linguagens regulares é fechada sob a operação união. Prova: A idéia é combinar dois AFNs N1 e N2 que aceitam as linguagens regulares A1 e A2 em um AFN N para provar que A1 U A2 é regular. O autômato N tem um novo estado inicial que ramifica para os estados iniciais de N1 e N2 com setas ε. Então a nova máquina caminha pelas duas máquinas nãodeterministicamente para advinhar qual das duas aceita a entrada, se uma aceitar, N também aceita. N1 = (Q1,∑,δ1,q1,F1) reconhece A1. N2 = (Q2,∑,δ2,q2,F2) reconhece A2. N = (Q,∑,δ,q0,F) que reconhece A1 U A2 será: ● Q = {q0} U Q1 U Q2 ○ É o novo estado q0 somado aos estados de N1 e N2. ● q0 = q0 : Estado inicial de N ● F = F1 U F2 ● δ é definido de mode que para qualquer q ∈ Q e qualquer a ∈ ∑ε temos: δ(q,a) = { δ1(q,a) para q ∈ Q1 { δ2(q,a) para q ∈ Q2 { {q1,q2} para q = q0 e a = ε { Ø para q = q0 e a ≠ ε Teorema 1.47 A classe das linguagens regulares é fechada sob a operação concatenação. Prova: Queremos provar que um autômato N formado a partir de N1 e N2 reconhece A1 ० A2. O estado inicial de N será o estado inicial de N1 e os estados de aceitação de N1 são ligados por setas ε ao estado inicial de N2. Os estados de aceitação de N serão os estados de aceitação de N2. N1 = (Q1,∑,δ1,q1,F1) reconhece A1. N2 = (Q2,∑,δ2,q2,F2) reconhece A2. N = (Q,∑,δ,q0,F) que reconhece A1 ० A2 será: ● Q = Q1 U Q2 ● q0 = q1 : Estado inicial de N1 ● F = F2 ● δ é definido de mode que para qualquer q ∈ Q e qualquer a ∈ ∑ε temos: δ(q,a) = { δ1(q,a) para q ∈ Q1 e q ∉ F1 { δ1(q,a) para q ∈ F1 e a ≠ ε { δ1(q,a) U {q2} para q ∈ F1 e a = ε { δ2(q,a) para q ∈ Q2 Teorema 1.49 A classe das linguagens regulares é fechada sob a operação estrela. Prova: Temos uma linguagem regular A1 e queremos provar que A1* também é regular. O AFN N reconhecerá A1*. N pode ser construído como N1 com setas ε retornando ao estado inicial a partir dos estados de aceitação. E N também deve ser modificado para que aceite ε, que é sempre um membro de A*. Assim, adicionase um novo estado inicial que também é de aceitação e que tenha uma seta ε para o antigo estado inicial.N1 = (Q1,∑,δ1,q1,F1) reconhece A1. N = (Q,∑,δ,q0,F) que reconhece A1* será: ● Q = Q1 U {q0} ● q0 = q0 : Novo estado inicial ● F = {q0} U F1 ● δ é definido de mode que para qualquer q ∈ Q e qualquer a ∈ ∑ε temos: δ(q,a) = { δ1(q,a) para q ∈ Q1 e q ∉ F1 { δ1(q,a) para q ∈ F1 e a ≠ ε { δ1(q,a) U {q1} para q ∈ F1 e a = ε { {q1} para q = q0 e a = ε { Ø para q = q0 e a ≠ ε 1.3 Expressões Regulares Podemos usar operações regulares para montar expressões descrevendo linguagens chamadas expressões regulares, como por exemplo: ● (0 U 1)0* = Uma linguagem constituída de todas as cadeias começando com 0 ou 1 e seguidas por um número qualquer de 0s. ○ (0 U 1) = ({0} U {1}) : Conjuntos 0 e 1 = L = {0,1} ○ 0* = {0}* = Todas as cadeias com qualquer número de 0s. ○ O símbolo de concatenação (०) é omitido como o de multiplicação (x) em álgebra: (0 U 1)0* = (0 U 1) ० 0* Seja ∑ = {0,1}, a expressão regular ∑ = (0 U 1) descreve a linguagem constituída de todas as cadeias de comprimento 1 sobre esse alfabeto e ∑* descreve uma linguagem que constituída de todas as cadeias sobre ∑. ∑*1 contém todas as cadeias terminadas em 1. (0∑*)U(∑*1) consiste de todas as cadeias que começam com 0 e terminam com 1. Seqüência de operandos correta a menos que parênteses sejam usados mudando a ordem: 1. Estrela 2. Concatenação 3. União Definição Formal de Uma Expressão Regular R é uma expressão regular se R for: 1. a para algum a no alfabeto ∑ = linguagem {a}, 2. ε = linguagem {ε}, ○ Linguagem contendo uma única cadeia, a cadeia vazia. 3. Ø = linguagem vazia, ○ Linguagem que não contém nenhuma cadeia. 4. (R1 U R2) onde R1 e R2 são expressões regulares, 5. (R1 ० R2) onde R1 e R2 são expressões regulares, ou 6. (R1*) onde R1 é uma expressão regular. Exemplos: ● R+ é a abreviação de RR*. Ou seja, R* tem todas as cadeias que são 0 ou mais concatenações de cadeias de R, e R+ tem todas as cadeias que resultam de 1 ou mais concatenações de cadeias de R. ○ R+ U ε = R*. ○ L(R) = linguagem que descreve a expressão regular R. ● 0*10* = {w | w contém um único 1} ● (0U1)* = {0, 1, 00, 01, 10, 11, …..} ● (abUa)* = {ab, a, abab, aba, aab, aa, …..} ● ∑*1∑* = {w | w tem pelo menos um símbolo 1} ● ∑*001∑* = {w | w contém a subcadeia 001} ● 1*(01+)* = {w | todo 0 em w é seguido por pelo menos um 1} ● (∑∑)* = {w | w é uma cadeia com comprimento par} ● (∑∑∑)* = {w | o comprimento de w é um múltiplo de 3} ● 01 U 10 = {01, 10} ● 0∑*0 U 1∑*1 U 0U1 = {w | w começa e termina com o mesmo símbolo} ● (0 U ε)1* = 01* U 1* = {w | w contém um 0 ou ε antes de toda cadeia de 1*} ● (0 U ε)(1 U ε) = {ε, 0, 1, 01} ● 1*Ø = Ø ○ Conjunto vazio concatenado com qualquer conjunto é um conjunto vazio ● Ø* = {ε} Teorema 1.54 Uma linguagem é regular se e somente se uma expressão regular a descreve. Lema 1.55 Se uma linguagem é descrita por uma expressão regular, então ela é regular. Prova: O David eh meu heroi! A prova é feita a partir dos 6 casos na descrição formal de expressões regulares. Constróise um AFN para cada um dos casos. Lema 1.60 Se uma linguagem é regular, então ela é descrita por uma expressão regular. Prova: Se A é uma linguagem regular, então uma expressão regular a descreve. Vamos utilizar um AFNG, Autômato Finito NãoDeterminístico Generalizado. Convertemos AFDs em AFNGs e depois, AFNGs em expressões regulares. AFNG: São AFNs cujas setas de transição podem quaisquer expressões regulares como rótulos. Ele lê blocos de símbolos da entrada. Suas características são: ● O estado inicial tem setas de transição para todos os estados mas não recebe seta de estado nenhum. ● Só existe um estado de aceitação no qual chegam setas de todos os estados e dele não sai nenhuma seta. Não pode ser o mesmo que o estado inicial. ● Todos os estados tem setas ligando todos os estados, com exceção do estado inicial e do de aceitação. Para construir esse AFNG, adicionase um novo estado inicial com uma seta ε apontando para o antigo estado inicial e um novo estado de aceitação com setas ε chegando dos antigos estados de aceitação. Adicionase setas com rótulo Ø entre estados que não tenham setas.O David eh meu heroi! Devemos reduzir os estados do AFNG até ter somente o estado inicial e o estado de aceitação para convertêlo em uma expressão regular. Fazemos isso selecionando um estado qualquer, removendoo e reparando a máquina alterando as expressões regulares que rotulam cada uma das setas restantes de modo que a mesma linguagem ainda seja reconhecida. a nova seta ligando qi e qj é uma expressão regular que descreve todas as cadeias que levariam qi a qj, seja passando pelo estado removido ou diretamente. O AFNG só difere do AFN somente pela função de transição: δ: (Q {qaceita) X (Q {qinício}) → R R é a coleção de todas as expressões regulares sobre o alfabeto ∑. Se δ(qi,qj) = R, a seta do estado qi para o estado qj tem a expressão regular R como rótulo. Definição Formal de AFNG: É uma 5upla (Conjunto de estados, alfabeto de entrada, regras para movimentação, estado inicial e estado de aceitação; (Q,∑,δ,qinicio,aceita)) onde: ● Q = o conjunto finito conhecido como os estados; ● ∑ = alfabeto de entrada; ● δ: (Q {qaceita) X (Q {qinício}) → R = função de transição; ● qinicio = estado inicial; ● qaceita = estado de aceitação; Definição Formal de Computação: Seja N = (Q,∑,δ,q0,F) um AFNG e w seja uma cadeia do alfabeto ∑*. N aceita w se w = w1w2w3...wn onde cada wi é membro do alfabeto ∑* e existe uma seqüência de estados q0, q1, …, qk em Q com 3 condições: 7. q0 = qinicio ➢ A máquina começa no estado inicial. 8. Para cada i, wi ∈ L(Ri), onde R = δ(qii, qi) ➢ Ri é a expressão regular sobre a seta que vai de qi1 a qi. 9. qk = q ➢ A máquina aceita sua entrada se o último estado é de aceitação. 1.4 Expressões Regulares Lema do Bombeamento para Linguagens Regulares É um teorema que afirma que todas as linguagens regulares têm uma propriedade especial. Se mostrarmos que uma linguagem não tem essa propriedade, temos a garantia de que ela não é regular. A propriedade diz que todas as cadeias da linguagem podem ser bombeadas se elas são no mínimo tão longas quanto um valor p, chamado de comprimento de bombeamento. Quer dizer que cada uma dessas cadeias contém uma parte que pode ser repetida um número qualquer de vezes com a cadeia resultante permanecendo na linguagem. O David eh meu heroi! Teorema 1.70 Lema do Bombeamento Se A é uma linguagem regular, então existe um número p (comprimento de bombeamento) tal que, se s é qualquer cadeia de A de comprimento no mínimo p, então s pode ser dividida em 3 partes, s = xyz, satisfazendo as seguintes condições: 1. para cada i ≥ 0, ∈ A,y zx i 2. |y| > 0, ○ y ≠ ε 3. |xy| ≤ p |s| representa o comprimento da cadeia s e significa que i cópias de y são concatenadasyi entre si, e = ε.y0 Capítulo 2 2.1 Gramáticas LivresdoContexto ● Regras de substituição, ou Produções: ○ cada regra aparece como uma linha na gramática, compreendendo um símbolo e uma cadeia separadas por uma seta. ● Variável: ○ São os símbolos, geralmente representadas por letras maiúsculas. As cadeias são constituídas de variáveis e outros símbolos chamados de terminais. ● Terminais: ○ representados por letras minúsculas. ● Variável Inicial: ○ Uma variável que ocorre do lado esquerdo da primeira regra. ● Derivação: ○ Sequência de substituições para obter uma cadeia. ● Linguagem LivredoContexto (LCC): ○ Linguagem gerada por uma Gramática LivredoContexto. Exemplo: G1: A → 0A1 A → B B → # ou G1: A → 0A1 | B B → # A,B = Variáveis 0,1,# = Terminais A = Variável Inicial Forma a cadeia 000#111 L(G1) = Conjunto de cadeias geradas por G1 (Linguagem da gramática G1) L(G1) = { # | n ≥ 0}0n 1n Pelo Lema do Bombeamento, w = # → L(G1) é nãoregular.0p 1p Uma derivação da cadeia 000#111 na gramática G1 é: A ⇒ 0A1 ⇒ 00A11 ⇒ 000A111 ⇒ 000B111 ⇒ 000#111 Definição Formal de uma Gramática LivredoContexto: É uma 4upla (V,∑,R,S)) onde: ● V = o conjunto finito e nãovazio conhecido como os variáveis; ● ∑ = um conjunto finito disjunto de V denominado terminais; ○ Pode usar ε. ○ Equivale ao alfabeto nas linguagens regulares ● R: Um conjunto finito de regras, com cada regra sendo uma variável e uma cadeia de variáveis e terminais; ○ A → u onde A ∈ V e u ∈ (V U ∑)* ● S: Variável inicial; ○ S ∈ V Se A → w é uma regra de GLC, dizemos que: ● uAv origina uwv : uAv ⇒ uwv, onde u,v ∈ (V U ∑)* ● u deriva v: u ⇒* v se u = v ou se existe uma sequência u1, u2, …, uk com k ≥ 0 e u1 ⇒ u2 ⇒ … ⇒ uk ⇒ v ● A Linguagem da Gramática é: {w ∈ ∑* | S ⇒* w} Exemplo: G3 = ({S}, {a,b}, R, S) onde o conjunto de regras R é: S → aSb | SS | ε A gramática G3 forma cadias como ab, abab, aaabbb, aababb… Pense em “a” como “(“ e em b como “)”. Exemplo: G4: = (V, ∑, R, <EXPR>) onde: V = { <EXPR>, <TERM>, <FACTOR>} ∑ = {a, +, x, (, )} R = <EXPR> → <EXPR> + <TERM> | <TERM> <TERM> → <TERM> x <FACTOR> | <FACTOR> <FACTOR> → (<EXPR>) | a as cadeias a+a x a e (a+a) x a podem ser geradas por G4. Gramática Sensível ao Contexto: A substituição depende do contexto. Como no exemplo abaixo onde temos condições especiais na substituição de A (precedido de 1 e 0). Exemplo: A → 0A0 A → 1A0 1A0 → 1AA0 0A0 → 0BA0 1B1 → 1#1 Projetando Gramáticas LivresdoContexto 1. Simplificar construindo gramáticas individuais para cada parte: S → S1 | S2 | … | Sk, onde Si são variáveis iniciais para as gramáticas individuais. Por exemplo, para obter uma gramática para a linguagem { | n ≥ 0} U { | n ≥ 0}, primeiro construir a0n 1n 1n 0n gramática: a. S1 → 0S11 | ε para { | n ≥ 0}. E depois:0 n 1n b. S2 → 1S20 | ε para { | n ≥ 0}. Depois adicionamos a regra S → S1 | S2 para1 n 0n formar: S → S1 | S2 S1 → 0S11 | ε S2 → 1S20 | ε 2. Construir primeiro um AFD para uma linguagem regular para depois construir uma GLC. a. Pegar uma variácel Ri para cada estado qi do AFD. b. Adicionar a regra Ri → aRj à GLC se δ(qi,a) = qj. c. Adicionar Ri → ε se qi ∈ F. d. R0 é a variável inicial da gramática onde q0 é o estado inicial da máquina. 3. Cadeias com subcadeias ligadas no sentido de uma máquina para uma linguagem precisa memorizar uma quantidade ilimitada de informação sobre uma das subcadeias para verificar se ela corresponde à outra subcadeia. a. Por exemplo, { | n ≥ 0}, onde temos que verificar se o número de 0s é igual0n 1n ao de 1s. Construir uma GLC que lide com isso com uma regra da forma R → uRv que fera cadeias onde a parte contendo “u” corresponde à parte contendo “v”. Ambiguidade ● Derivação mais à esquerda: se a cada passo a variável remanescente mais à esquerda é aquela que é substituída. ● Uma cadeia w é derivada ambiguamente em uma gramática se ela tem duas ou mais derivações mais a esquerda diferentes. ● Gramática Ambígua: Gera alguma cadeia ambiguamente. ● Linguagem Inerentemente ambígua: LLCs geradas apenas por gramáticas ambíguas. Teorema A classe das linguagens livresdocontexto é fechada sob as operação regulares (União, Concatenação e Estrela). Prova: Para os 3 casos, temos uma prova por construção. Lembrando que a classe das LLCs não é fechada sobre a Intersecção nem a complementação. Seja L1 e L2 Linguagens LivresdoContexto geradas respectivamente pelas gramátivas G1 = (V1, ∑, R1, S1) e G2 = (V2, ∑, R2, S2) com V1 e V2 disjuntos: L1 = ∑*01 L2 = { | n ≥ 0}0n 1n G1: S1 → X01 X → 1X | 0X | ε G2: S2 → 0S21 | ε 1) L1 U L2: G: S → S1 | S2 S1 → X01 X → 1X | 0X | ε S2 → 0S21 | ε G = (V, ∑, R, S) onde V = V1 U V2 U {S}, S ∉ V1 e S ∉ V2 ∑ = é o mesmo. R = R1 U R2 U {r1, r2}, r1: S → S1, r2: S → S2 ou R = R1 U R2 U {r0}, r0: S → S1 | S2 2) L1 ० L2: G: S → S1S2 S1 → X01 X → 1X | 0X | ε S2 → 0S21 | ε G = (V, ∑, R, S) onde V = V1 U V2 U {S}, S ∉ V1 e S ∉ V2 ∑ = é o mesmo. R = R1 U R2 U {r0}, r0: S → S1S2 3) L1*: G: S → S1S | ε S1 → X01 X → 1X | 0X | ε G = (V, ∑, R, S) onde V = V1 U {S}, S ∉ V1 ∑ = é o mesmo. R = R1 U {r1, r2}, r1: S → S1S, r2: S → ε Exemplo: GLC para , onde L = { | n ≥ 0}L 0n 1n =L { | n > m ≥ 0} U0n 1m { | m > n ≥ 0} U0n 1m {w | w contém a subcadeia 10} = L1 U L2 U L3L G1: S1 → 0S11 | 0S1 | 0 G2: S2 → 0S21 | S21 | 1 G3: S3 → X10X X → 0X | 1X | ε G: S → S1 | S2 | S3 S1 → 0S11 | 0S1 | 0 S2 → 0S21 | S21 | 1 S3 → X10X X → 0X | 1X | ε Teorema Se L é regular, então é LivredoContexto. Prova: Se L é regular, então existe um AFD M = (Q, ∑, δ, q0, F) que a reconhece. A partir de M, podemos construir uma GLC G = (V, ∑, R, S) equivalente. A prova é por construção, então vamos pegar como exemplo o AFD que reconhece L = {w | w contém a subcadeia 101}, com ∑ = {0,1}: Q = {q0, q1, q2, q3} F = {q3} δ 0 1 q0 q0 q1 q1 q2 q1 q2 q0 q3 q3 q3 q3 Para construir uma GLC a partir de um AFD: ● V = Q = {q0, q1, q2, q3} ● Pegar uma variável Ri para cadaestado qi do AFD e adicionar a regra Ri → aRj à GLC se δ(qi,a) = qj .Adicionar Ri → ε se qi ∈ F: R: q0 → 0q0 | 1q1 q1 → 0q2 | 1q1 q2 → 0q0 | 1q3 q3 → 0q3 | 1q3 q3 → ε ● R0 é a variável inicial da gramática onde q0 é o estado inicial da máquina. S = q0 Definição Formal de Computação: Se w = w1w2...wn ∈ L, então existe uma sequência de estados r0, r1, r2, …, rn tal que: 1. r0 = q0 ➢ A máquina começa no estado inicial. 2. ri+1 = δ(r1, wi+1) para i = 0, 1, …, n1 ➢ r1 = δ(r0, w1) e existe a regra r0 → w1r1 3. rn ∈ F ➢ A máquina aceita sua entrada se o último estado é de aceitação. w é gerado pela GLC, com derivação: r0 ⇒ w1r1 ⇒ w1w2r2 ⇒ … ⇒ w1w2...wnrn ⇒ w1w2...wn Exemplos de GLCs: 1) L = {a,b}* S → aS | bS | ε S ⇒ aS ⇒ abS ⇒ abaS ⇒ aba para w = aba 2) L = ∑*ab∑*a S → TabTa T → aT | bT | ε 3) L = { | n, m ≥ 0}an bm cn+m S → A | ε A → aAc | B | ε B → bBc | ε ou S → aSb | B B → bBc | ε 4) L = { | m ≥ n ≥ 1}an bm S → aAb A → aAb | B B → Bb | ε 5) L = {w | w contém a mesma quantidade de as e bs} S → aSb | bSa | SS | ε Seja w = axa onde w possui a mesma quantidade de as e bs | a | a | b | a | b | a | b | a | a | b | b | b | b | a | 0 1 2 1 2 1 2 1 2 3 2 1 0 1 0 ● Um contador que incrementa a cada “a” e decresce a cada “b”. Começando e terminando com “a”, o contador vai começar e terminar com 0 e deve ter um outro 0 no caminho. Forma Normal de Chomsky Uma GLC está na forma normal de Chomsky se toda regra é da forma: A → BC A → a onde “a” é qualquer terminal e A, B, C são variáveis, com A sendo a variável inicial. Ainda podemos usar a regra S → ε onde S é a variável inicial. Teorema 2.9 Qualquer linguagem livredocontexto é gerada por uma GLC na forma normal de Chomsky. Pode se converter qualquer gramática G na forma normal de Chomsky seguindo os passos: 1. Adicionase uma nova variável inicia para garantir que a variável inicial nunca apareça do lado direito; 2. Eliminase toda regra ε da forma A → ε (exceto S0 → ε caso exista); 3. Eliminase toda regra unitária da forma A → B; 4. Corrigese a gramática para que ela continue gerando a mesma linguagem; Prova: 1. Criamos uma variável inicial S0 ∉ V e a regra S0 → S. A nova gramática é G = (Q, V’, R’, S) onde: V’ = V U {S0} R’ = R U {S0 → S} 2. Removemos toda regra da forma A → ε em que A não é a variável inicial. Então, para cada ocorrência de A no lado direito, adicionamos uma nova regra com essa regra apagada. Ou seja, se temos R → uAv, devemos adicionar a regra R → uv. Isso é feito para cada ocorrência de A, de modo que R → uAvAw faz com que adicionemos: R → uAvw, R → uvAw, R → uvw Se tivermos a regra R → A, adicionamos a regra R → ε sem criar regras já eliminadas. Isso é repetido até eliminar todas as regras ε que não envolvem a variável inicial. Lembrando que u é uma cadeia de variáveis e terminais. 3. Removemos as regras unitárias A → B. Ou seja, para cada A → B, se temos B → u aparece, adicionamos a regra A → u e eliminamos A → B. 4. Eliminamos as regras mistas da forma A → u, onde u contém pelo menos um terminal e |u| ≥ 2. Então, para cada regra A → u, a cada terminal “a” em “u”, adicionamos a regra W1 → a e substituímos u por W1 em u (A → W1). 5. Eliminar as regras compridas. Bi ∈ V. Substituímos cada regra A → B1B2...Bk (k ≥ 3) por: A → B1C1 C1 → B2C2 C2 → B3C3 Ck2 → Bk1Bk Exemplo 2.10: Supomos a GLC G6, vamos convertêla para a forma normal de Chomsky seguindo os passos acima. As regras em azul acabaram de ser adicionadas. E as regras em vermelho acabaram de ser removidas: 1. G6 original está a esquerda. Adicionamos ma nova variável inicial: S → ASA | aB S0 → S A → B | S S → ASA | aB B → b | ε A → B | S B → b | ε 2. Removemos as regras ε B → ε, mostrado a esquerda, e A → ε, mostrado a direita: S0 → S S0 → S S → ASA | aB | a S → ASA | aB | a | SA | AS | S A → B | S | ε A → B | S | ε B → b | ε B → b 3. a. Removemos as regras unitárias S → S mostrada à esquerda, e S0 → S mostrada à direita: S0 → S S0 → S | ASA | aB | a | SA | AS S → ASA | aB | a | SA | AS | S S → ASA | aB | a | SA | AS A → B | S A → B | S B → b B → b b. Removemos as regras unitárias A → B e A → S: S0 → ASA | aB | a | SA | ASS0 → ASA | aB | a | SA | AS S → ASA | aB | a | SA | ASS → ASA | aB | a | SA | AS A → B | S | b A → S | b | ASA | aB | a | SA | AS B → b B → b 4. Convertemos as regras remanescentes para a forma apropriada. A gramática a seguir é equivalente a G6. S0 → AA1 | UB | a | SA | AS S → AA1 | UB | a | SA | AS A → b | AA1 | UB | a | SA | AS A1 → SA U → a B → b Exemplo: G7 é a seguinte gramática: S → SXS | ε X → ab | ε 1. Após aplicar o passo 1, temos: S0 → S S → SXS | ε X → ab | ε 2. Após aplicar o passo 2, temos: S0 → S | ε S → SXS | SS | XS | SX | X X → ab 3. Após aplicar o passo 3, temos: S0 → SXS | SS | XS | SX | ab | ε S → SXS | SS | XS | SX | ab X → ab 4. Após aplicar o passo 4, temos: S0 → SXS | SS | XS | SX | AB | ε S → SXS | SS | XS | SX | AB X → AB A → a B → b 5. Após aplicar o passo 5, temos: S0 → ST | SS | XS | SX | AB | ε S → ST | SS | XS | SX | AB X → AB T → XS A → a B → b Exemplo: G8 é a seguinte gramática: S → ASA | aB A → B | S B → b | ε 1. Após aplicar o passo 1, temos: S0 → S S → ASA | aB A → B | S B → b | ε 2. Após aplicar o passo 2, temos: S0 → S S → ASA | aB | a A → B | S | ε B → b S0 → S S → ASA | SA | AS | aB | a A → B | S B → b 3. Após aplicar o passo 3, temos: S0 → ASA | SA | AS | aB | a S → ASA | SA | AS | aB | a A → b | ASA | SA | AS | aB | a B → b 4. Após aplicar o passo 4, temos: S0 → ASA | SA | AS | XB | a S → ASA | SA | AS | XB | a A → b | ASA | SA | AS | XB | a B → b X → a 5. Após aplicar o passo 5, temos: S0 → AY | SA | AS | XB | a S → AY | SA | AS | XB | a A → b | AY | SA | AS | XB | a Y → SA B → b X → a Problema 2.26: Mostre que, se G for uma GLC na forma normal de Chomsky, então para qualquer cadeia w ∈ L(G) de comprimento n ≥ 1, exatamente 2n 1 passos são necessários para qualquer derivação de w usando G. Se n = 0, exatamente um passo é necessário. Exemplo: G: S → ASA | aB A → B | S B → b | ε w = bbabbb ∈ L(G) S ⇒ ASA ⇒ AASAA ⇒ AAaBAA ⇒* bbabbb |w| = 6. Usando a forma normal de Chomsky, precisamos exatamente de 2x61 = 11 passos paraderivar w. Prova: Se n ≥ 1: Para gerar uma cadeia w com |w| = n≥ 1, temos que fazer n substituições usando regras da forma A → a para produzir terminais. Precisamos também produzir n1 variáveis, usando regras da forma A → BC. Cada substituição aumenta em 1 a quantidade de variáveis. Partindo da variável inicial, precisamos n1 substituições para obter n variáveis no total. Total de substituições = n + n1 = 2n 1. Se n 0, então w = ε. ε é gerado usando a substituição S → ε. Problema da Pertinência: Dada uma GLC G e uma cadeia w. w ∈ L(G)? Resposta: É possível saber se w ∈ L(G) usando o seguinte algoritmo: 1. Transforme G em uma GLC G’ equivalente na forma normal de Chomsky; 2. Se |w| ≥ 1, gere uma lista de todas as cadeias com 2|w|1 substituições Se w está nessa lista, então w ∈ L(G), se não, não; 3. Se |w| = 0, verifique se a regra S0 → ε está em G’ (ou gere todas as cadeias com 1 substituição e verifique se ε é uma delas); 2.2 Autômatos com Pilha São Autômatos Finitos NãoDeterminísticos com um componente extra chamado pilha que provê memória adicional além da memória finita disponível no controle e permite que o autômato reconheça linguagens nãoregulares. ● São equivalentes em poder a GLCs. ● Pode escrever símbolos sobre a fita e lêlos mais tarde. ● A pilha começa vazia. E o autômato aceita se ao final da cadeia de entrada ele se encontra em um estado de aceitação mesmo se a pilha não estiver vazia. Propriedades: 1. Todo AFN pode ser considerado um AP que ignora a pilha. a. Para toda linguagem regular, existe um AP que a reconhece. 2. Uma linguagem é livredocontexto se se somente se um AP a reconhece. a. Para toda linguagem livredocontexto existe um AP que a reconhece e para toda GLC, existe um AP equivalente. b. A linguagem reconhecida por todo AP é livredocontexto. Para todo AP existe uma GLC equivalente. Exemplo 1: L = {anbn | n ≥ 0} 1. Para cada símbolo ‘a’ lido, empilhamos um símbolo ‘x’; 2. Para cada símbolo ‘b’ lido, desempilhamos um símbolo ‘x’; 3. Se ao final da cadeia a pilha está vazia, então a quantidade de ‘a’ é a mesma de ‘b’; w1 = aabb → aceita. w2 = aaba → não aceita. w3 = aabbb → não aceita (por não ter mais x para desempilhar). w4 = aab → aceita (a máquina para num estado de aceitação). Exemplo 2: L = {anbn | n ≥ 0} Exemplo 3: L = {wwR | w ∈ {a,b}*} Exemplo 4: L = {w | w contém a mesma quantidade de ‘a’ e ‘b’} Exemplo 5: L = {w | w ∈ {(,)}* e w é uma cadeia de parênteses corretamente encaixados} Exemplo 6: L = {aibjck | i, j, k ≥ 0 e i = j ou i = k} Definição Formal de Autômato com Pilha (NãoDeterminístico): É uma 6upla P = (Q,∑,Γ,δ,q0,F) onde: ● Q = Conjunto de estados; ● ∑ = Alfabeto de entrada; ● Γ = Alfabeto da pilha; ○ Γ pode ser (Γ = ∑); ● δ = Função de transição; ● q0 = Estado inicial (q0 ∈ Q); ● F = Conjunto de estados de aceitação (F ⊆ Q); ■ δ é definido por: δ: Q x ∑ε x Γε → P(Q x Γε) = δ: Q x ∑ε x desempilha → P(Q x empilha); ■ a,b → c = lê, desempilha, empilha; Lembrando que: ∑ε = ∑ U {ε}; Γε = Γ U {ε}; δ(qi,a,x) = {(qj,y), (qp,z)} Definição Formal de Computação: Um AP P = (Q,∑,Γ,δ,q0,F) aceita a cadeia w ∈ ∑* se podemos se w = w1w2...wn, com wi ∈ ∑* e existe uma sequência de estados r0, r1, r2, …, rn e uma sequência de cadeias s0, s1, s2, …, sn com si ∈ Γ* tal que: 1. r0 = q0, s0 = ε; ➢ P inicia no estado inicial e com a pilha vazia. 2. (ri+1, b) ∈ δ(ri, wi+1, a) ➢ P se move conforme o estado, a pilha e o próximo símbolo de entrada. ➢ i = 0, 1, 2, …, n1; ➢ si = at e si+1 = bt com a, b ∈ Γε e t ∈ Γ* 3. rn ∈ F ➢ O estado de aceitação ocorre ao final da entrada. Exemplo: Utilizando o exemplo 1, onde L = {anbn | n ≥ 0}, w = aabb Sequência de estados é: q0, q1, q1, q1, q2, q2, q2, q3 = εaaεbbε → k símbolos e k+1 estados (7 símbolos, 8 estados). Sequência de cadeia em Si = ε, $, x$, xx$, x$, $, ε 1. Estado inicial = q0 e s0 = ε; 2. (q1, $) ∈ δ(q0, ε, ε) para (i = 0); s0 = ε; s1 = $ (q1,x) ∈ δ(q1, a, ε) para (i = 1); s1 = $; s2 = x$; 3. q3 ∈ F; Teorema 2.20 Uma linguagem é livre do contexto se e somente se um autômato com pilha a reconhece. (Duas provas para dois lemas, ida e volta). Lema 2.21: Se uma linguagem é livre do contexto, então alguma autômato com pilha a reconhece. Prova: O AP que descreveremos aceitará uma entrada w gerada por uma GLC G determinando se existe uma dericação para w. O AP começa escrevendo empilhando $ e a variável inicial na pilha, passando por várias cadeias intermediárias e fazendo várias substituições. Em algum momento ele pode chegar contendo somente símbolos terminais, o que significa que a GLC foi usada para derivar a cadeia. Então o AP aceita se essa cadeia for idêntica a cadeia de entrada. Os passos são: 1. Colocar $ e a variável inicial na pilha; 2. Loop: a. Se o topo da pilha é uma variável “A”, nãodeterministicamente selecione uma das regras de A e substitua A pela cadeia do lado direito da regra. b. Se o topo da pilha é um terminal “a”, leia o próximo símbolo da entrada e compareo com “a”. Se eles são iguais, repita. Se não são, rejeite nesse ramo nãodeterminístico. c. Se o topo da pilha é $, entre no estado de aceitação e a entrada é aceita se ela tiver sido toda lida. Um jeito de abreviar a ação de empilhar uma cadeia ao invés de um símbolo na pilha dentro das regras de transição é acrescentar novos estados entre um estado e outro: (r, xyz) ∈ δ(q, a, s); Dada uma GLC = (V,∑,R,S), queremos um AP P = (Q,∑,Γ,δ,q0,F) equivalente. O AP deve aceitar as mesmas cadeias geradas pela GLC. ● Q = {qinício, qlaço, qaceita} U E, onde E = conjunto de estados para implementar a abreviação acima; ● Γ = ∑ U V U {$}; ● q0 = qinício; ● F = {qaceita}; ● δ é definido por: 1. δ(qinício, ε, ε) = {(qlaço, S$)} 2. Laço: a. δ(qlaço, ε, A) = {(qlaço, w) | A→w é regra onde A ∈ V, w ∈ (V U ∑)*}; b. δ(qlaço, a, a) = {(qlaço, ε)} c. δ(qlaço, ε, $) = {(qaceita, ε)} ● E = {q1, q2, q3, q4, q5}Para :S → aSb | bSb | ε Como no livro, podemos simplificar para: Teorema Roda linguagem regular também é livredocontexto. Prova: L regular → existe um AFD que reconhece L → existe um AFN equivalente → existe um AP equivalente → existe uma GLC equivalente → L é LivredoContexto. 2.3 Linguagens NãoLivresdoContexto Lema do Bombeamento para LLCs. Teorema 2.34 Se A é uma LLC, então existe um número p (comprimento de bombeamento) onde, se s é uma cadeia em A de comprimento pelo menos p, então s pode ser dividida em 5 partes (s = uvxyz) que satisfazem as condições: 1. para cada i ≥ 0, uvixyiz ∈ A; ● Uma mesma variável gera vxy em sua ocorrência mais alta e somente x em sua ocorrência mais baixa. 2. |vy| > 0 (v ≠ ε ou y ≠ ε) 3. |vxy| ≤ p; Prova: G é a GLC que gera a LLC A. “b” é o número máximo de símbolos do lado direito de uma regra. Na árvore sintática, um nó não pode ter mais que “b” filhos, ou seja, no máximo “b” folhas estão a um passo da variável inicial; no máximo b2 folhas estão a 2 passos da variável inicial; e no máximo bh folhas estão a “h” passos da variável inicial. Então se a altura da árvore sintática é no máximo h, o comprimento de bombeamento p da cadeia gerada é no máximo bh. Uma árvore sintática de altura h gera uma cadeia de comprimento máximo bh. ● Altura (h): Quantidade de substituições da primeira à última substituição. ● Altura ≤ h ⇒ |w| ≤ bh ● |w| > bh ⇒ altura > h ● |V| = Número de variáveis em G e p = b|V| + 1: ○ Então se w é uma cadeia em A, e seu comprimento é p ou mais, ela tem que ter altura no mínimo |V|+1. Para todo w ∈ L, com |w| ≥ p, a altura da árvore é ≥ |V|+1: |w| ≥ p ⇒ altura ≥ |V|+1. Se altura ≥ |V|+1, o caminho de maior comprimento da variável inicial até uma folha contém pelo menos |V|+1 variáveis, ou seja, alguma variável está repetida. Se b = 0, a GLC é S → ε, então L = {ε} e p = 1. (Satisfaz o lema por vacuidade) Se b = 1, a GLC é S → A, A → B, B → C… e L = {a,b,c,...,z,ε}, que pode conter ε e cadeias de comprimento 1. A prova é válida para b ≥ 2: |w| ≥ bh+1 = |w| ≥ bh+b b ≥ 2 ⇒ |w| > bh |w| ≥ bh+1 ⇒ |w| > bh ⇒ altura ⇒ h |w| ≥ bh+1 ⇒ altura > h |w| ≥ bh+1 ⇒ altura ≥ h+1 Exemplo: L = {0n#1n} | n≥ 0} S → 0S1 S → B B → # w = 000#111 Exemplo: S → AB A → aA | bB | ε B → abBba | ε Exemplo: L = {anbncn | n ≥ 0} Suponha L é uma LLC. Existe p > 0 (comprimento de bombeamento). w = apbpcp = cadeia de teste. Começamos com a condição 3) que nos diz que |vxy| ≤ p e vamos analizar os casos onde isso acontece: caso 1) vxy contém somente ‘a’s caso 2) vxy contém ‘a’s e ‘b’s caso 3) vxy contém somente ‘b’s caso 4) vxy contém ‘b’s e ‘c’s caso 5) vxy contém somente ‘c’s caso 1) vy = ak (1≤ k ≤ p) uxz = apkbpcp ∉ L caso 2) vy = akbj (1 ≤ k+j ≤ p) uxz = apkbplcp ∉ L caso 3) vy = bk (1≤ k ≤ p) uxz = apbpkcp ∉ L caso 4) vy = bkcj (1 ≤ k+j ≤ p) uxz = apbpkcpj ∉ L caso 5) vy = ck (1≤ k ≤ p) uxz = apbpcpk ∉ L Exemplo: L = {ww | w ∈ {a,b}*} w = apbpapbp → w ∈ L e |w| = 4p ≥ p Começamos novamente pela condição 3 para verificar os casos: 1) Se vxy contém símbolos de ambas as metades, vy contém k ‘a’s e j ‘b’s (0 < k+j ≤ p). Bombeando para baixo: uxz = apbpjapkbp ∉ L. a) Se j > k: A primeira metade começa com a e a segunda com b. b) Se k > j: A primeira metade termina com a e a segunda com b. c) Se k = j: As duas metades são diferentes. Portanto, uxz ∉ L. Exemplo: L = {wwR | w ∈ {a,b}*} L é LLC pois S → aSa | bSb | ε gera L. L = {ε, aa, bb, aaaa, abba, …} L satisfaz o lema: p = 1 (valor mínimo, pois toda cadeia w ∈ L, |w| ≥ 1 tem a forma: Onde s ∈ {a,b}*. ● uvvxyyz = saaaasR ∈ L Exemplo: L = {anbmcn+m | n,m ≥ 0} L é LLC pois : S → aSc | A A → bAc | ε Exemplo: L = {anbmcnm | n,m ≥ 0} L não é LLC. Prova: Suponha L sendo LLC e p > 0. w = apbpcp2 w ∈ L e |w| = 2p + p2 ≥ p 1) vxy contém somente ‘a’s e ‘b’s : k ‘a’s e j ‘b’s (k ≠ 0 ou j ≠ 0). Bombeando para baixo: uxz = apkbpjcp2 → p2 ≠ (pk)*(pj) 2) vxy contém somente ‘c’s. ck, k > 0: uxz = apbpcp2k → p2k ≠ p*p 3) vxy contém k ‘b’s e j ‘c’s (k ≠ 0 ou j ≠ 0): uxz = apbpkcp2l p2 j = p*(pk) ? p2 j = p2 pk pk = j ? 1. Se k = 0, j ≠ 0 e uxz ∉ L (caso 2) 2. Se k ≠ 0, j = 0 e uxz ∉ L (caso 1) 3. Se k ≠ 0 e j ≠ 0, pk > j → uxz ∉ L 4. Se k = 1, j < p e pk > j, uxz ∉ L 5. Se k > 1, j < p e pk > l, uxz ∉ L Exemplo: L = {akbiaibjajbk | i, j, k ≥ 0} L é LLC pois: S → aSb | A A → BB B → bBa | ε Exemplo: L = {w#x | w,x ∈ {a,b}* e w é uma subcadeia de x} L = {#, a#a, a#ab, abb#aabbb,...} Não é LLC. Prova: Suponha LLC, e p o comprimento de bombeamento. w = apbp#apbp aaa...aaabbb...bbb#aaa...aaabbb...bbb vxy 1) vxy contém ak e bj antes de #. Bombeando para cima: uvvxyyz = ap+kbp+j#apbp ∉ L pois ap+kbp+j não é subcadeia de apbp 2) vxy contém ak e bj depois de #. Bombeando para baixo: uxz = apbp#apkbpj ∉ L pois apbp não é subcadeia de apkbpj 3) vxy contém o símbolo # a) Se v ou y contém #, bombeando para baixo: uxz não contém # e ∉ L. b) x contém #. Então v = bk e y = aj, com k ≠ 0 ou j ≠ 0. Bombeando para baixo: uxz = apbpk#apjbj Se j ≠ 0, apbpk não é subcadeia de apjbp Bombeando para cima: uvvxyyz = apbp+k#ap+jbj Se k =≠ 0, apbp+k não é subcadeia de ap+jbp Exemplo: L = {wR#x | w,x ∈ {a,b}* e w é uma subcadeia de x} = {abb#aabbaaa, …} S → AB B → aB | bB | ε A → aAa | bAb| C C → Ca | Cb | # Capítulo 3 3.1 Máquina de Turing (MT determinística) Em cada passo da sua operação: 1. Lê um símbolo da fita; 2. De acordo com o estado atual e o símbolo lido: a. Escreve o símbolo (na mesma posição); b. Muda de estado ou não; c. Desloca a cabeça de leitura/escrita uma posiçãopara a direita ou esquerda. ● A fita é semiinfinita; ● Inicialmente, a cabeça da leitura/escritura está no extremo esquerdo da fita; ● Possui um único estado de aceitação e um único estado de rejeição; ● A MT para imediatamente quando chega a um estado de aceitação ou rejeição; ● Se a MT não para nunca, dizemos que entrou em loop; ● MT pode ler e escrever “brancos” ⊔. A linguagem de uma MT = conjunto de cadeias que ela aceita. Se L1 = L(M), dizemos que M reconhece L1. Definição Formal de Máquina de Turing : É uma 7upla M = (Q,∑,Γ,δ,q0,qaceita,qrejeita) onde: ● Q = Conjunto de estados; ● ∑ = Alfabeto de entrada; ○ sem o símbolo em branco ⊔ ● Γ = Alfabeto da fita; ○ ⊔ ∈ Γ e ∑ ⊆ Γ ● δ = Função de transição; ● q0 = Estado inicial (q0 ∈ Q); ● qaceita = estado de aceitação; ● qrejeita = estado de rejeição; ■ δ é definido por: δ: Q’ x Γ → Q x Γ x {E,D} Q’ = Q {qaceita,qrejeita} Exemplo: MT que reconhece L = {w#w | w ∈ {a,b}*} → L não é LLC w = aabb#aabb ∈ L xabb#aabb xabb#xabb xxbb#xabb xxbb#xxbb ∑ = {a,b,#} Γ = {a,b,#,x,⊔} Definição de Configuração de uma MT: Representação do estado atual, conteúdo da fita e posição da cabeça da leitura/escritura. Exemplo: 1011q701111 → a fita é 101101111, o estado atual é q7 e a cabeça está sobre o segundo 0. Exemplo: ● uaqibv origina uqjacv se na função de transição δ(qi, b) = (qj, c, E) ● uaqibv origina uacqjv se na função de transição δ(qi, b) = (qj, c, D) Exemplo: ● A configuração qibv origina qjcv se na função de transição δ(qi, b) = (qj, c, E) ● A configuração uaqi (uaqi⊔) origina ua⊔qj se na função de transição δ(qi, ⊔) = (qj, ⊔, D Definição Formal de Computação: Uma MT M = (Q,∑,Γ,δ,q0,qaceita,qrejeita) aceita (rejeita) uma cadeia w = w1w2...wn, com wi ∈ ∑ se existe uma sequência de configurações C0, C1, C2, …, Cn tal que: 1. C0 é a configuração inicial q0w; 2. Ci origina Ci+1 segundo a função de transição; 3. Cn é uma configuração de aceitação (rejeição); Exemplos de MT: Exemplo 1: MT que decide (aceita w ∈ A e rejeita w ∉ A) a linguagem A = {02^n | n ≥ 0 } = {0,00,0000,000000,...} Nesse caso, a MT sempre para. M = “Sobre a cadeia de entrada w: 1. Faça uma varredura da esquerda a direita, marcando um 0 não e um sim. 2. Se no estágio 1 a fita contém um único 0, aceite. 3. Se no estágio 1, a fita contém mais de um 0 em uma quantidade ímpar, rejeite. 4. Retorne ao extremo esquerdo da fita. 5. Vá para o estágio 1. ∑ = {0}, Γ = {0,@,X,⊔} Exemplo 2: MT ENDMARK → Recebe uma cadeia w, escreve o símbolo @ na frente de w para ∑ = {0,1} Exemplo 3: MT EQUAL → Decide a linguagem L = {w | w possui a mesma quantidade de 0’s e 1’s} Exemplo 4: MT EVEN → Recebe uma cadeia de entrada w que representa um número binário n. Aceita se n for par e rejeita se n for ímpar. Exemplo 5: MT LEFTEND → Dada uma entrada @w, coloca a cabeça sobre o primeiro símbolo de w e para. Exemplo 5: MT NEXTLEX → Recebe @w e retorna @u, onde u é o sucessor lexicográfico de w. Exemplo 6: MT INCR → f(n) = n+1 Exemplo 7: MT COPY → Recebe @w e retorna @w#w Exemplo 8: MT ENUM → Enumera (lista) cadeuas de {0,1}* em ordem lexicográfica. ##0#1#00#01#10#... Exemplo 8: MT COMP → Recebe @w1#w2, e retorna @1 se w1 < w2 ou @0 se w1 ≥ w2, onde w1 e w2 representam números binários n1 e n2. Computa a função f(n1, n2) = 1, se n1 , n2; 0, se n1 ≥ n2. f(1110#11100) = 1 f(11100#01100 = 0 ∑ = {@,0,1,#} Γ = {@,0,1,#,⊔, 0º,1º} M = “Sobre a entrada @w1#w2: 1. Se os comprimentos w1 e w2 não são iguais, insira 0’s na frente da cadeia mais curta para que ambas fiquem do mesmo tamanho. 2. Compare os dígitos mais à esquerda de cada cadeia. 3. Se o dígito mais à esquerda de w1 é 0, e o de w2 é 1, apague a fita exceto @, escreva 1 e pare. 4. Se o dígito mais à esquerda de w1 é 1, e o de w2 é 0, apague a fita exceto @, escreva 0 e pare. 5. Se são iguais, substitua ambos por X e compare os próximos dígitos de cada cadeia. 6. Repita até achar dígitos diferentes ou chega ao fim das cadeias. 7. Apague a fita exceto @, escreva 0 e pare.” Exemplo 9: MT que decide C = {aj, bj, ck | i*j = k e i,j,k ≥1} M = “Sore a cadeia de entrada w: 1. Verifique se w tem a forma anbncn. Se não tiver, rejeite. 2. Marque um a, vá e volte entre b’s e c’s marcando um de cada até esgotar os b’s. Se todos os c’s foram marcados, rejeite. 3. Apague as marcas sobre os b’s, repita o passo dois para cada “a”, Se todos os a’s forem marcados, veja se todos os c’s também foram marcados. Se sim, aceite, se não, rejeite. Exemplo 10: MT ADD → Recebe w1#w2, e retorna w3, onde wi representam números binários ni, e n3 = n1 + n2 (Computa a função f(n1,n2) = n1 + n2) M = “Sobre a entrada w1#w2: 1. No final da cadeia entrada, adicione #0. 2. Rode COMP sobre w2 e 0 3. Se w2 > 0, rode INCR sobre w1 e DECR sobre w2. 4. Repita até obter w2 = 0. 5. Apague tudo exceto w1” Exemplo 11: MT MULT → f(n1,n2) = n11*n2 M = “Sobre a entrada w1#w2: 1. No final da entrada escreva #0#0, o primeiro 0 é X. 2. Rode COMP sobre w2 e o segundo 0. 3. Se w2 > 0: a. Rode COPY para criar uma cópia de w1 no final. b. Rode ADD para adicionar w1 a X. c. Rode DECR sobre w2. 4. Repita até w2 = 0. 5. Apague tudo exceto X. Exemplo 12: MT SQRT → f(n) = {sqrt(n), se n é um quadrado perfeito | maior inteiro n tal que m ≤ sqrt(n), se n não é um quadrado perfeito}: f(25) = 5, f(18) = 4 M = “Sobre a entrada w: 1. No final da entrada escreva #0. Chame ao 0 de X. 2. Rode COPY para criar 2 cópias de X. 3. Rode MULT para multiplicar as duas cópias de X e obter Y = X*X. 4. Rode COMP para comparar Y com w. 5. Se y ≤ w, rode INCR sobre X. 6. Repita os passos 25 até Y > w. 7. Rode DECR sobre X 8. Apague tudo exceto X” Variantes de Máquinas de Turing: 1) MT M1 na qual a cabeça de leitura/escrita pode não deslocar. Função de transição = δ: Q’ x Γ → Q x Γ x {E,D,P} Q’ = Q {qaceita,qrejeita} Teorema Para toda MT M1 existe uma MT regular M2 equivalente. Prova: Para cada transição δ(qi,a) = (qj,b,P) de M1, M2 realiza as transições: δ(qi,a) = (qi’,b,D) δ(qi’,c) = (qj,c,E) para todo c ∈ Γ. 2) MT Multifita Função de transição = δ: Q’ x Γ1 x Γ2 x … x Γk → Q x Γ1 x Γ2 x … x Γk x {E,D}k Teorema Para tida MT de k fitas, existe uma MT de uma fita equivalente Prova: A MT regular simula as k fitas em uma única fita da seguinte forma: Γ = {0,1,a,b,x,@,⊔,#,0º,1º,aº,bº,xº,@º,⊔º} 3) MT com fita infinita para os dois sentidos Teorema Para toda MT infinita para os dois sentidos, existe uma MT regular equivalente.Prova: Podemos simular esta MT com uma MT com duas fitas. Toda MT com fita em ambos sentidos possui uma MT de duas fitas equivalente. Toda MT com duas fitas possui uma MT regular equivalente. 4) MT nãodeterminística Função de transição = δ: Q’ x Γ → P(Q x Γ x {E,D}) Se pelo menos um ramo da árvore leva ao estado de aceitação, a MT aceita a entrada. Se todos os ramos válidos levam a estados de rejeição, a MT rejeita. (Busca por nível). Teorema Para toda MT nãodeterminística existe uma MT determinística equivalente. Prova: Seja uma MT nãodeterminística M. Construímos uma MT N determinística equivalente usando 3 fitas: Fita 1: Recebe a cadeia de entrada, e não é modificada. Fita 2: Fita de simulação. Fita 3: Fita endereço → (MT ENUM) Ordem lexicográfica → índice do ramo não determinístico. A fita 3 trabalha com um alfabeto ∑ = {1,2,3} (maior quantidade de bifurcações possíveis), enumerando cadeias sobre ∑3 em ordem lexicográfica. Teorema Para toda MT com qualquer variante que alguém tenha considerado alguma vez, ou possa considerar no futuro, existe uma MT regular equivalente. Corolário Uma linguagem é TuringReconhecível (decidível) se e somente se uma MT Variante a reconhece. Prova para MT Multifita: L é Decidível → uma MT com uma única fita decide L → Essa MT também é multifita, com k =1 → uma MT multifita decide L. L é decidido por uma MT multifita → existe uma MT com uma única fita equivalente → Essa MT é decide L → L é decidível. Enumeradores: 1. MT ENUM → Enumera cadeias sobre ∑ em ordem lexicográfica. G = “Sobre a entrada w: 1. Ignore a entrada e apague a fita e escreva # no início da fita 2. Começando por s = ε, escreva s# na fita 3. Copie S a direita do último # 4. Substitua o último s pelo seu sucessor lexicográfico, e adicione # a direita 5. Volte ao passo 2, e repita indefinidamente.” 2. MT que enumera cadeias da linguagem L = {w | w contém uma quantidade ímpar de 1’s} → L é regular = 0*1(0*10*1)*0* ∑ = {0,1} L = {1,01,10,001, 010,...} MT com 3 fitas: E = “Sobre a entrada w: 1. Apague a fita 1 (as outras já começam vazias) 2. Rode o enumerador G para gerar cadeias si ∈ ∑*, na fita 2.. Para cada cadeia si gerada: a. Apague a fita 3 e escreva 1 na fita 3 b. Faça uma varredura sobre si cada vez que leia 1, troque o 1 na fita 3 por 0, ou o 0 por 1. c. Ao chegar no final de si, leia a fita 3. Se contiver 00, escreva # a direita do conteúdo da fita 1 e copie a cadeia si parar a fita 1. Se a fita 3 contém 10, volte ao passo 2 para gerar outra cadeia.” 3. MT que enumera L = { w | w contém a subcadeia 111 } → L é regular = ∑*111∑* Teorema Uma linguagem é decidível se e somente se um enumerador a enumera em ordem lexicográfica Prova: 1) Se L é decidível, então é enumerável em ordem lexicográfica. Se existe a MT D que decide L, então podemos construir o enumerador E da seguinte forma: E = “Sobre a entrada w: 1. Ignore a entrada. 2. Rode ENUM para gerar cadeias sobre ∑ em ordem lexicográfica. Para cada cadeia gerada si: a. Rode D sobre si. Se aceita, imprima si”. 2) Seja L enumerável lexicograficamente, com enumerador E, construímos uma MT D que decide L: D = “Sobre a entrada w: 1. Rode E para gerar cadeias si ∈ L. Para cadeias si: a. Compare si e w. Se w < si, rejeite. b. Se w = si, aceite. Se w > si, volte ao passo 1 para gerar a próxima cadeia si.” Teorema Uma linguagem é TuringReconhecível se e somente se uma enumerador a enumera. Prova: 1) L é enumerável. Construímos uma MT que reconhece L. R = “Sobre a entrada w: 1. Rode E para gerar cadeias si ∈ L. Para cada cadeia si: a. Compare si e w. b. Se si = w, aceite. Se si ≠ w, volte ao passo 1.” 2) L é TuringReconhecível. Construímos um enumerador para L. Fecho sobre operações: A classe das linguagens decidíveis é fechada sobre: 1) União 2) Intersecção 3) Complementação 4) Concatenação 5) Operação estrela Sejam L1 e L2 decidíveis e D1 e D2 as MTs que as decidem. Complementação: D = “Sobre a entrada w: 1. Rode D1 sobre w. Se Aceita, rejeita, se rejeita, aceite” Concatenação: D = “sobre a entrada w: 1. Para cada forma de subdividir w na forma w = w1w2: a. Rode D1 sobre w1. Se aceita, rode D2 sobre w2. Se D2 aceita, aceite. 2. Se todas as subdivisões foram testadas e nenhuma foi aceita, rejeite. União: Intersecção: Estrela: D = “Sobre a entrada w: 1. Sobre cada forma de subdividir w = w1,w2,...wk, onde os wi são subcadeias: a. Rode D1 sobre cada wi. Se D1 aceita todos os wi, aceite. 2. Se todas as subdivisões forem listadas, rejeite. Capítulo 4 4.1 Linguagens Decidíveis Problemas decidíveis concernentes a Linguagens Regulares Vamos analisar algoritmos que testam se um autômato finito aceita uma cadeia, se a linguagem de um AFD é vazia e se dois AFDs são equivalentes. Vamos mostrar pelos teoremas 4.1, 4.2 e 4.3 que entregar à MT um AFD, um AFN ou uma expressão regular é a mesma coisa, pois podemos converter uma codificação na outra. Problema da aceitação: Expresso pela linguagem AAFD que testa se um AFD específico aceita uma dada cadeia. AAFD = {<B,w> | B é um AFD que aceita a cadeia de entrada w} → Testamos se <B,w> é membro da linguagem AAFD. (Se o AFD B aceita a entrada w). Mostrar que a linguagem é decidível é o mesmo que mostrar que o problema computacional é decidível. Teorema 4.1 AAFD é uma linguagem decidível. Prova: Construímos uma MT M que decide AAFD. M = “Sobre a entrada <B,w>, onde B é um AFD, e w é uma cadeia: 1. Simule B sobre a entrada w. 2. Se a simulação termina em um estado de aceitação, aceite; Se não, rejeite.” É o mesmo que imaginar um programa que realiza uma simulação. A entrada <B,w> é uma representação do AFD B (uma lista de seus 5 componentes Q, ∑, δ, q0, F) e de uma cadeia w. Ao receber a entrada, M determina primeiro se o AFD B está representado apropriadamente, se não estiver, M rejeita. M realiza a simulação mantendo o registro do estado atual de B e da posição atual de B na entrada w escrevendo essa informação na sua fita. Teorema 4.2 AAFN é uma linguagem decidível. Prova: AAFN = {<B,w> | B é um AFN que aceita a cadeia de entrada w} Construímos uma MT N que decide AAFN e convertemos o AFN B para um AFD equivalente C, fazendo N usar M como subrotina. N = “Sobre a entrada <B,w> onde B é um AFN, e w é uma cadeia: 1. Converta o AFN B para um AFD equivalente C usando o procedimento do Teorema 1.39. 2. Rode a MT M sobre <C,w>. 3. Se M aceita, aceite, Se M rejeita, rejeite. Teorema 4.3 AEXR é uma linguagem decidível. Prova: AEXR = {<R,w> | R é uma expressão regular que gera a cadeia w} Construímos
Compartilhar