********************************** ********** TEO - Resumo ********** ********************************** Data : 02/09/2003 a 07/12/2003 Versão : 04/07/2007 Professor: Francisco Aurélio de Souza Grossi Autor : Leandro Salvador ( leandrosalvador.com.br ) * Índice - Conjuntos - Alfabetos - Gramáticas - Linguagem e Gramática - Hierarquia de Chomsky - Gramáticas Regulares (GR) (tipo 3) - Expressões Regulares (ER) - Autômatos Finitos (AF) - Autômatos Finitos Determinísticos (AFD) - Transições e Configurações (I) - AFD - Transdutor Finito Determinístico (TFD) - Autômatos Finitos Não-Determinísticos (AFN) - Transições e Configurações (I) - AFN - AFD x AFN - Algoritmo para AFN - Eliminação de Indeterminismos (AFN --> AFD) - Gramática --> AFN - AFN --> Gramática - ER --> AFN - AFN --> ER - Algoritmo de Minimização (número de estados) - Algoritmo de Minimização (4 passos) - Resumo - GLD --> AFN - Gramáticas Livres de Contexto (GLC) (tipo 2) - Árvores Sintáticas - Autômato com Pilha (AFP) - Reconhecedores de LLC's - Formalismo dos AFP's - Transições e Configurações - AFP - Diagramas de Estado - AFP - Gramáticas Sensíveis a Contexto (GSC) (tipo 1) - Gramáticas com Estrutura de Frase (GEF)(tipo 0) - Reconhecedores - Autômato Adaptativo - Máquina de Turing (MT) - Modelo de MT - Transições e Configurações - MT - Diagrama de Estados - MT - Outros Exemplos na Apostila - Resumo * Conjuntos - não há membros repetidos nem uma ordem estabelecida - notações a E A --> a é um membro do conjunto A a !E A --> a não é um membro do conjunto A A C B --> conjunto A está contido no conjunto B; A é um subconjunto de B; todos os membros de A também pertencem ao conjunto B A !C B --> conjunto A contém conjunto B; A é um superconjunto de B - dois conjuntos são iguais se A C B e A !C B - A = {x : p(x)} --> conjunto A é composto de membros com a propriedade p - A = {x : x = 2k, k >= 0} --> números pares não negativos - A = {x : x = 2k + 1, k >= 0} --> números ímpares não negativos * Alfabetos - é representado pela letra grega sigma maiúscula (E) - alfabeto é um conjunto finito de símbolos - uma sentença sobre um alfabeto é uma seqüência finita de símbolos deste alfabeto - a sentença vazia é representada pela letra lambda minúscula (T) - notações referentes a alfabetos E* --> conjunto de todas as sentenças possíveis sobre E, inclusive vazia E+ --> conjunto de todas as sentenças possíveis sobre E, exceto vazia - por definição E* = E+ U {T} E+ = E* - {T} - exemplos 1) E = {a, b} E+ = {a, b, aa, ab, ba, bb, aaa, ...} E* = {T, a, b, aa, ab, ba, bb, aaa, ...} 2) E = {a, b} se w pertence E conseqüentemente w = a ou w = b se w pertence E+ conseqüentemente w = a ou w = b ou w = aa ou w = ab ou w = aaabbb ou ... - OBS: apenas nesse tópico "Alfabetos" utilizaremos - a letra T para representar lambda minúscula - a letra E para representar sigma maiúscula * Gramáticas - linguagem formal é um conjunto de sentenças sobre um alfabeto - gramática é um dispositivo gerador de sentenças de uma linguagem - a gramática é definida como uma quádrupla (ou quadra) - G = (V,T,P,S) = (não-terminais, terminais, regra de produção, símbolo inicial) - V --> conjunto finito de símbolos não-terminais (ou variáveis) - T --> conjunto finito de símbolos terminais - P --> conjunto finito de pares, denominados regras de produção, tal que o primeiro componente é uma sentença de (V U T)+ e o segundo componente é uma sentença de (V U T)* - S --> membro de V (S E V) denominado variável inicial ou símbolo inicial - uma regra de produção (a, b) é representada por a --> b * Linguagem e Gramática - uma gramática é um formalismo de geração das sentenças de uma linguagem - a linguagem gerada por uma gramática G, denotada por L(G), é o conjunto de todas as sentenças constituídas exclusivamente de símbolos terminais derivadas a partir do símbolo inicial S - duas gramáticas são equivalentes se geram linguagens iguais - L(G1) = L(G2) <==> G1 e G2 são equivalentes - exemplo 1) L(G) = {w E T* : S ==>+ w} - { --> conjunto - w --> variável - T* --> sentenças - : --> tal que - S --> símbolo inicial - ==>+ --> deriva 2) G = (V,T,P,S) = (não-terminais, terminais, regra de produção, símbolo inicial) G = ({A,B}, {0,1}, {A --> 0A, A --> B, B --> 1B, B --> T}, A} ou então V = {A,B} T = {0,1} P = {A --> 0A A --> B B --> 1B B --> T (OBS: T = sentença vazia) } A ==> 0A ==> 00A ==> 000A ==> 000B ==> 0001B ==> 00011B ==> 00011 A ==>7 00011 3) G = ({S,A,B,C}, {a,b,c}, P, S) P = {S --> BAb | CAc A --> BA | a B --> b C --> c } - linguagem gerada por G n n L(G) = {b ab : n > 0} U {cb ac : n >= 0} - para produzir "cbbac" S ==> CAc ==> CBAc ==> CBBAc ==> CBBac ==> CBbac ==> Cbbac ==> cbbac 4) G = ({S,A}, {a,b,c}, P, S} P = {S --> bAb | cAc A --> bA | a } - linguagem gerada por G n n L(G) = {b ab : n > 0} U {cb ac : n >= 0} m n p 5) L(G) = {a b c : m,n,p >= 0} P = {A --> aA | ab | T B --> bB | bC | T C --> cC | T } - gramática que gera L(G) G = ({A,B,C}, {a,b,c}, P, A) * Hierarquia de Chomsky - Chomsky classificou as gramáticas e respectivas linguagens em quatro tipos - GR --> Gramáticas Regulares - (tipo 3) - GLC --> Gramáticas Livres de Contexto - (tipo 2) - GSC --> Gramáticas Sensíveis a Contexto - (tipo 1) - GEF --> Gramáticas com Estrutura de Frase - (tipo 0) - a única diferença entre os diferentes tipos de gramática são as regras de produção - G = (V,T,P,S) - P --> regras de produção --> única diferença - hierarquia ______________________ / ________________ \ / / __________ \ \ / / / ____ \ \ \ ( GEF ( GSC ( GLC ( GR ) ) ) ) \ \ \ ¯¯¯¯ / / / \ \ ¯¯¯¯¯¯¯¯¯¯ / / \ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ / ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ * Gramáticas Regulares (GR) (tipo 3) - GLD - Gramática Linear à Direita - regras de produção A --> wB A --> w - w --> seqüência de símbolos terminais - B --> símbolo não terminal A,B E V w E T* - T* --> seqüência de símbolos terminais, inclusive o vazio - lado esquerdo consiste de uma única variável - lado direito consiste de um número qualquer de terminais (inclusive zero) seguido de uma única variável - GLE - Gramática Linear à Esquerda - regras de produção A --> Bw A --> w A,B E V w E T* - GLUD (utilizada nos exemplos) - Gramática Linear Unitária à Direita - é GLD e, adicionalmente, |w| <= 1 - regras de produção A --> aB A --> a A,B E V a E T* - GLUE - Gramática Linear Unitária à Esquerda - é GLE e, adicionalmente, |w| <= 1 - regras de produção A --> Ba A --> a A,B E V a E T* - GLD x GLUD - GLD A --> abc A --> abcB - GLUD A --> a A --> aB - exemplo 1) G = ({B}, {0,1}, {B --> 0B, B --> 1B, B --> T}, B) - gramática para números binários 2) G = ({S}, {a, b}, {S --> aS, S --> b}, S) L(G) = {a^n b : n >= 0} 3) G = ({S,A}, {a,b,c}, P, S) P = {S --> aS, S --> bA, A --> c} L(G) = {a^n bc : n >= 0} 4) G = ({D,I), {+,-,0,1,2,3,4,5,6,7,8,9}, P, I) P = {I --> +D I --> -D D --> 0D | 1D | 2D | 3D | 4D | 5D | 6D | 7D | 8D | 9D D --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 L(G) = {números inteiros com sinal e com zeros à esquerda} 5) G = ({S,A,B}, {0,1}, P, S} P = {S --> 0A S --> 1B A --> 0A A --> 0 B --> 1B B --> 1 } L(G) = {0^n : n >= 0} U {1^m : m >= 0} 6) Construir uma gramática sobre {a,b,c} que gera uma linguagem cujas sentenças não contêm seqüências repetidas de nenhum símbolo G = ({A,B,C}, {a,b,c}, P, A) P = {A --> aB | a | T B --> bC | B C --> cA | c } 7) Construir uma gramática regular cuja linguagem seja o conjunto dos números inteiros pares positivos com zeros à esquerda G = ({D}, {0,1,2,3,4,5,6,7,8,9}, P, D) P = {D --> 0D | 1D | 2D | 3D | 4D | 5D | 6D | 7D | 8D | 9D D --> 0 | 2 | 4 | 6 | 8 } 8) Construir uma gramática regular cuja linguagem seja o conjunto dos números inteiros pares positivos sem zeros à esquerda G = ({N,D}, {0,1,2,3,4,5,6,7,8,9}, P, N) P = {N --> 1D | 2D | 3D | 4D | 5D | 6D | 7D | 8D | 9D D --> 0D | 1D | 2D | 3D | 4D | 5D | 6D | 7D | 8D | 9D D --> 0 | 2 | 4 | 6 | 8 } 9) Construir uma gramática regular cuja linguagem seja o conjunto dos números binários terminados em 00 G = ({B,C}, {0,1}, P, B) P = {B --> 0B | 1B | 0C C --> 0 } - linguagem gerada por G L(G) = {w E T* : S ==>+ w} - para produzir "00100" B ==> 0B ==> 00B ==> 001B ==> 0010C ==> 00100 - expressão regular (0 | 1) * 00 - exemplo --> 00000 * Expressões Regulares (ER) - é uma outra maneira de descrever uma linguagem regular - definição - dado um alfabeto E (sigma) qualquer - qualquer símbolo de E, além de T (sentença vazia), é Expressão Regular - se x e y são ER x* é ER (zero ou mais instâncias de x) x+ é ER (uma ou mais instâncias de x) (x) é ER xy é ER (concatenação) x|y é ER (união) - ordem de precedência ^ *, + | concatenação E (. "ponto" ou "nada") | união OU (| "pipe") - exemplo 1) E = {a,b} a* = {T, a, aa, aaa, aaaa, ...} a+ = aa* = {a, aa, aaa, aaaa, ...} (aa)* = {T, aa, aaaa, aaaaaa, ...} a | bc* = {a, b, bc, bcc, bccc, ...} (ab)* = {T, ab, abab, ababab, ...} (a|b)* = {T, a, b, ab, aaa, aab, ...} - exemplo E = {0,1} 2) Sentenças com pelo menos três 1's L(G) = 0*10*10*1(0|1)* - exemplo --> 00001T1000100000 3) Sentenças com comprimento no máximo 3 L(G) = (T|0|1).(T|0|1).(T|0|1) 4) Sentenças com número par de 0's ou exatamente dois 1's L(G) = ((00)* 1*)* | 0*10*10*0* ----------- --- ---------- número par ou exatamente de 0's dois 1's - exemplo E = {a,b,c} 5) Qualquer sentença com não mais que três a's - sentença com 0, 1, 2 ou 3 a's --> (a|T)(a|T)(a|T) - x são sentenças sem a --> x(a|T)x(a|T)x(a|T)x - x = (b|c)* L(G) = (b|c)*(a|T)(b|c)*(a|T)(b|c)*(a|T)(b|c)* 6) Qualquer sentença que contenha, no máximo, dois a's consecutivos - contem 0, 1 ou 2 a's --> (b|c)*(a|aa|T)(b|c)* L(G) = (b|c)*(a|aa|T)(b|c)* ((b|c)+(a|aa|T)(b|c)*)* 7) Qualquer sentença em que o número de a's consecutivos é múltiplo de 3 L(G) = (aaa|b|c)* * Autômatos Finitos (AF) - são mecanismos formais que reconhecem (sim | não) as sentenças de uma determinada linguagem regular - uma linguagem é regular se for reconhecida por um autômato finito e vice-versa - AFD --> Autômato Finito Determinístico (tem um único sentido determinado a seguir) - AFND --> Autômato Finito Não Determinístico - o autômato finito só pára quando terminar a sentença de entrada - representação gráfica (diagrama de estados) - estado inicial --> -->(q0) - estado intermediário --> (q1) - estado final --> ((q2)) - transição --> (qi)-----a----->(q1) - significado --> estando no estado qi (corrente), a leitura do símbolo "a" da fita de entrada causa a transição para o estado q1 - loop --> |_^ a,b - quando passar pelo estado final não necessariamente o autômato pára - mas quando o autômato pára, ele necessariamente está no estado final - exemplo 1) Um AFD que só aceita números binários iniciados por 1 -->(A)-----1----->((B)) --> se entrar nesse loop a sentença é aceita, | |_^ pois "morrerá" no estado final | 0,1 | '------0------>(C) --> se entrar nesse loop a sentença não é aceita, |_^ pois "morrerá" num estado que não é o final 0,1 2) Um AFD que só aceita números binários sem 0 à esquerda -->(A)-----1----->((B)) | |_^ | 0,1 | '------0----->((C))-----0,1----->(D) |_^ 0,1 - se entrar 1 e mais algum outro número, aceita - se entrar apenas 0, aceita - se entrar 0 e mais algum outro número, não aceita - nesse caso, 0... significa 0 à esquerda - o número 0 sozinho não é 0 à esquerda, por isso é aceito 3) L(G) = {a^n b^m : n >= 0, m >= 0} -->((I))-----b----->((F)) |_^ |_^ a b 4) L(G) = {a^n b^n : n >= 0} - essa linguagem não é reconhecida por um autômato finito, pois a quantidade de a's é necessariamente igual à quantidade de b's, e o autômato finito não armazena a quantidade de loops - essa não é uma linguagem regular, mas sim uma linguagem não regular, conhecida como linguagem livre de contexto * Autômatos Finitos Determinísticos (AFD) - um AFD é uma quíntupla - M = (Q,E,d,q0,F) = (estados, alfabeto, função de transição, estado inicial, estados finais) - Q - conjunto finito de estados - E - sigma maiúscula - alfabeto finito de símbolos de entrada - d - delta minúscula - função de transição - d : Q . E --> Q - lê-se: cada estado Q deve ter uma transição para cada símbolo E resultando num único estado Q - exemplo E = {a,b,c} -----a----> -->(1)-----b---->((2)) -----c----> - q0 - estado inicial - q0 pertence Q - F - conjunto de estados finais - F está contido em Q - representações da função de transição d - diagrama de estados (dado) -----1-----> -->((q0)) (q1) ^ | <----1------ ^ | | | | | | | | | 0 0 0 0 | | | | | | | | | v -----1-----> | v (q2) (q3) <----1------ - tabela (representação 1) ---------------------- | estado | 0 | 1 | ---------------------- | q0 | q2 | q1 | | q1 | q3 | q0 | | q2 | q0 | q3 | | q3 | q1 | q2 | ---------------------- - estados correntes --> q0,q1,q2,q3 - símbolos de E --> 0,1 - estados após transição --> q2,q1,q3,q0,q0,q3,q1,q2 - tabela (representação 2) ------------------------------ | estado | símbolo | transição | ------------------------------ | q | ? per E | d(q,?) | ------------------------------ | q0 | 0 | q2 | | q0 | 1 | q1 | | q1 | 0 | q3 | | q1 | 1 | q0 | | q2 | 0 | q0 | | q2 | 1 | q3 | | q3 | 0 | q1 | | q3 | 1 | q2 | ------------------------------ - origem/consumo/destino (representação 3) d(q0,0) = q2 (lê-se: delta, estando em q0, consumindo 0, resulta em q2) d(q0,1) = q1 d(q1,0) = q3 d(q1,1) = q0 d(q2,0) = q0 d(q2,1) = q3 d(q3,0) = q1 d(q3,1) = q2 - definição formal de computação com AFD - seja M = (Q,E,d,q0,F) um Autômato Finito e w = w1 w2 w3 ... wn uma sentença do alfabeto E - diz-se que M aceita w se e somente se existir uma seqüência de estados r0,r1,r2,...,rn tal que - 1) r0 = q0 - começar no estado inicial - 2) d(ri,wi+1) = ri+1 (0 <= i <= n-1) - delta, estando em ri, consumindo wi+1, resulta em ri+1 - 3) rn E F - terminar no estado final - exemplo -->(r0)----w1--->(r1)----w2--->(r2) ... (rn-1)----wn---->((rn)) * Transições e Configurações (I) - AFD - a relação binária |- aplica-se a duas configurações de um autômato se e somente se a máquina puder passar de uma para a outra como resultado de uma única transição - configuração de um autômato é o par estado corrente e a subsentença da sentença de entrada a partir do símbolo corrente - exemplo (qi,aw) |- (qj,w) <==> a pertence E, w pertence E*, d(qi,a) = qj - onde (qi,aw) - mostra o AFD no estado qi com o símbolo corrente a seguido da subsentença w - a subsentença w pode ser vazia se a é o último símbolo |- - indica que a nova configuração é (qj,w) - pois o AFD transita para qj após consumir o símbolo a - a configuração (q,T) significa que o AFD consumiu toda a sentença e que sua operação terminou - define-se também (qi,w1) |-* (qj,w2) se (qi,w1) produz o estado qj após um número qualquer de transições, reduzindo a entrada de w1 para w2 - uma sentença w é aceita por um AFD M = (Q,E,d,q0,F) se há um estado q pertence F : (q0,w) |-* (q,T) - portanto, a linguagem reconhecida pelo AFD M é L(M) = {w pertence E* : (q0,w) |-* (qf,T), qf pertence F} - lê-se - a definição da linguagem que o autômato M aceita é - w é uma sentença de E*, - tal que partindo do estado inicial q0, - após um número qualquer de transições |-*, - atinjo um estado final qf, - tendo consumido todos os símbolos de w - (restando T e onde qf pertence ao conjunto dos estados finais F) - exercício 1) I = d(q1,a) = q1 (lê-se: delta, estando em q1, consumindo a, resulta em q1) d(q1,b) = q2 d(q2,a) = q1 d(q2,b) = q2 AF = a b |¯¯v |¯¯v -->(q1)-----b----->((q2)) <----a------ ER = (a|b)*b a) Teste a sentença "aaba" - seqüência de estados produzidas por "aaba" q1 q1 q1 q2 q1 - requisitos 1) r0 = q0 --> começar no estado inicial - o estado inicial é q1 - a seqüência começou em q1 - OK 2) d(r1,wi+1) = ri+1 - OK 3) rn E F --> terminar no estado final - o estado final é q2 - a seqüência terminou no estado q1 - NÃO OK - computação do autômato (q1,aaba) |- (q1,aba) |- (q1,ba) |- (q2,a) |- (q1,T) - conclusão - q1 !E F - a sentença "aaba" não é aceita pelo AFD b) Teste a sentença "aabab" - computação do autômato (q1,aabab) |- (q1,abab) |- (q1,bab) |- (q2,ab) |- (q1,b) |- (q2,T) - conclusão - q2 E F - a sentença "aabab" é aceita pelo AFD 2) AFD que aceita a linguagem cujas sentenças possuem "aa" ou "bb" como subsentenças - M = (Q,E,d,q0,F) = (estados, alfabeto, função de transição, estado inicial, estados finais) - M = ({q0,q1,q2,q3}, {a,b}, d, q0, {q3}) d: ---------------------- d(q0,a) = q1 | estado | a | b | d(q0,b) = q2 ---------------------- d(q1,a) = q3 | q0 | q1 | q2 | d(q1,b) = q2 | q1 | q3 | q2 | d(q2,a) = q1 | q2 | q1 | q3 | d(q2,b) = q3 | q3 | q3 | q3 | d(q3,a) = q3 ---------------------- d(q3,b) = q3 a) Escreva uma expressão regular que gera a linguagem L(M) - ER = (a|b)* aa|bb (a|b)** b) Desenhe o diagrama de estados que reconhece a linguagem L(M) -->(q0)-----a---->(q1) | / ^ | | / / | b b a a | / / | | / / | v v / v (q2)-----b---->((q3)) |__^ a,b 3) Construir um AFD que aceite L(M) = {w E {a,b}* : w não contém 3 b's consecutivos} a) Desenhe o diagrama de estados que reconhece a linguagem L(M) a a,b |¯¯¯v |¯v -->((1))-----b---->((2))-----b---->((3))-----b---->(4) ^ ^ | | | | | | | '------a------- | '----------------a---------------' b) Teste a sentença "aababba" - computação do autômato (1,aababba) |- (1,ababba) |- (1,babba) |- (2,abba) |- (1,bba) |- (2,ba) |- (3,a) |- (1,T) - 1 E F - conclusão - a sentença "aababba" é aceita pelo AFD - pois a computação do autômato termina no estado 1, e 1 pertence ao conjunto dos estados finais F * Transdutor Finito Determinístico (TFD) - é um dispositivo similar aos AFD's - tem o propósito de transformar sentenças de entrada em sentenças de saída - inicia em um estado inicial e transita de estado em estado, dependendo do argumento (estado e símbolo) como os AFD's - mas emite uma sentença de um alfabeto de saída em cada transição - não há estados finais - ele pára quando a sentença acaba - o rótulo de transição é expresso por a/w - que significa - consuma o símbolo a - mude de estado - emita a sentença w - AFD x TFD - autômato - diz se a sentença é ou não aceita - transdutor - tem um estado inicial e transforma a sentença em outra sentença - um TFD é uma quíntupla - M = (Q,E,G,d,q0) = (estados, alfabeto de entrada, alfabeto de saída, função de transição, estado inicial) - Q = AFD - E = AFD - G - gama maiúscula - alfabeto de saída - d - delta minúscula - função de transição - d : Q . E --> Q . G* - q0 = AFD - exercício 1) TFD que transmite todos os b's da palavra de entrada, mas elimina um a cada dois a's a) Desenhe o diagrama de estados b/b b/b |¯v |¯v -->(1)-----a/a---->(2) <----a/T----- b) Teste a sentença "abab" - entrada: abab - saída : abb * Autômatos Finitos Não-Determinísticos (AFN) - um AFN é uma quíntupla - M = (Q,E,d,q0,F) = (estados, alfabeto, função de transição, estado inicial, estados finais) - Q = AFD - E = AFD - d - delta minúscula - função de transição - d : Q . (E U {T}) --> 2^Q - exemplo (para explicar 2^Q) Q = {1,2,3} - 3 conjuntos 2^Q = {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} - 8 conjuntos 2^Q = 2^3 = 8 - q0 = AFD - F = AFD - representações da função de transição d - origem/consumo/destino (representação 3) d(q,a) = {q1,q2,q3,...,qn} - produz um conjunto de estados em vez de um único estado dos AFD's - este conjunto pode ser vazio, isto é, pode não haver estado de transição para o símbolo * Transições e Configurações (I) - AFN - de forma semelhante aos AFD's, a relação binária |- aplica-se entre duas configurações de um AFN - se um autômato M está no estado q e o próximo símbolo de entrada é a, então M pode seguir qualquer transição nas formas (q1,a,q2) --> um símbolo da entrada é consumido, no caso, o símbolo a (q1,T,q2) --> nenhum símbolo da entrada é consumido - exemplo (p,aw) |- (q,w) <==> a pertence (E U {T}), w pertence E*, q pertence d(p,a) - d(p,a) --> conjunto de estados - portanto, a linguagem reconhecida pelo AFN M é L(M) = {w pertence E* : (q0,w) |-* (qf,T), qf pertence F} ou então L(M) = {w pertence E* : d*(q0,w) intersecção F != 0} - d* corresponde a aplicações sucessivas da relação d * AFD x AFN - AFN não aumentam a capacidade de reconhecimento dos AFD's - os AFN's reconhecem as mesmas linguagens (regulares) que os AFD's reconhecem - o indeterminismo ajuda a expressar o autômato de uma maneira mais simples - qualquer AFN pode ser convertido para um AFD equivalente - o indeterminismo é a capacidade de alterar estados de uma maneira parcialmente determinada pelo estado corrente e símbolo de entrada - a relação de transição, ao processar uma configuração, pode causar uma transição para um conjunto de novos estados ao invés de apenas um estado como nos AFD's - o indeterminismo pode manifestar-se de duas formas - um ou mais estados de onde sai mais de uma flecha rotulada com o mesmo símbolo (q1 e q3) - quando o símbolo a ocorrer na entrada e o estado corrente for q1, por exemplo, pode-se transitar para q1 ou q2 - exemplo a,b a,b |¯v |¯v -->(q1)-----a---->(q2)-----a---->((q3)) <----b----- <----b----- - um ou mais estados de onde sai pelo menos uma flecha rotulada com T (vazio) - esta transição (em vazio) pode ocorrer sem consumir nenhum símbolo da entrada - exemplo a a,b |¯v -------------T-----------> |¯¯¯v -->(q1)-----b---->(q2)-----a---->((q3)) <----b----- - devido ao indeterminismo, a mesma sentença pode causar uma parada do AFN em mais de um estado, dependendo das transições escolhidas - considera-se a sentença aceita se pelo menos um destes possíveis estados for um estado final do AFN - um AFD é apenas um caso especial de AFN em que não há transições em vazio ou mais de uma transição com o mesmo símbolo em algum estado - ambos os dispositivos (AFD e AFN) reconhecem linguagens regulares e, embora AFN's sejam mais convenientes em alguns casos, eles têm o mesmo poder computacional dos AFD's - exemplo 1) Dada a linguagem cujas sentenças são repetições de ab e/ou aba a) ER = (ab | aba)* b) AFD <------------a------------- -->((1))-----a---->(2)-----b---->((3))-----a---->((4)) | | | <----b----- | | | | a | - o determinismo exige que duas | | | flechas saiam de cada estado | v | (correspondentes aos dois '-------b---->(5)<----b-------' símbolos do alfabeto) |_^ - o AFD não é trivial a,b c) AFN (duas alternativas) -->((1))-----a---->(2) - no estado 1 ele pode receber apenas a ^ <----b----- | - no estado 2 há duas alternativas | | - ou recebe b a b - ou recebe ba | | - terminando ou repetindo o ciclo '------(3)<----' d) AFN (transição vazia) -->((1))-----a---->(2) - como o AFN pode transitar para um ^ ^ | conjunto de estados, podem existir | | | transições proibidas (conjunto vazio) a T b | '----- | '-------(3)<----' - exercício 1) AFN que aceita números inteiros com sinal opcional a) Desenhe o diagrama de estados digito ---- + ---> |¯¯¯v -->(1)---- - --->(2)---digito-->((3)) ---- T ---> b) Teste a sentença "+235" - computação do autômato (1,+235) |- (2,235) |- (3,35) |- (3,5) |- (3,T) - conclusão - 3 E F - a sentença "+235" é aceita pelo AFN c) Teste a sentença "32" - computação do autômato (1,32) |- (2,32) |- (3,2) |- (3,T) - conclusão - 3 E F - a sentença "32" é aceita pelo AFN 2) AFN que aceita a linguagem cujas sentenças em {a,b} terminam em "aaa" - M = (Q,E,d,q0,F) = (estados, alfabeto, função de transição, estado inicial, estados finais) - M = ({1,2,3,4}, {a,b}, d, 1, {4}} d: ----------------------- d(1,a) = {1,2} | estado | a | b | d(1,b) = {1} ----------------------- d(2,a) = {3} | 1 | {1,2} | {1} | d(2,b) = T | 2 | {3} | T | d(3,a) = {4} | 3 | {4} | T | d(3,b) = T | 4 | T | T | d(4,a) = T ----------------------- d(4,b) = T a) Escreva uma expressão regular que gera a linguagem L(M) - ER = (a|b)* aaa b) Desenhe o diagrama de estados que reconhece a linguagem L(M) a,b |¯v -->(1)-----a---->(2)-----a---->(3)-----a---->((4)) * Algoritmo para AFN - algoritmo - A = {} - s = estado inicial - para cada estado a alcançável a partir de s - A = A U {a} - enquanto sentença não vazia - B = {} - leia símbolo x - para cada estado a em A - para cada transição T de a para algum estado b - B = B U {b} - para cada transição em x de a para algum estado b - B = B U {b} - para cada transição T de algum estado b E B para algum estado c !E B - B = B U {c} - A = B - se A intersecção F != {} - então retorna verdadeiro // aceita a sentença - senão // A intersecção F == {} - retorna falso // rejeita a sentença - após cada ciclo do "enquanto", o conjunto A contém todos os estados alcançáveis com o consumo de um símbolo da sentença - após a exaustão da sentença, basta verificar se um dos estados de A é final - exercício 1) AFN que aceita qualquer sentença que termine com "ab" ou "aba" a) Desenhe o diagrama de estados a a,b |¯v |¯v -->(q0)-----b---->(q1)-----a---->(q2) | -----T----> | | ^ | | | | b b b a | | | | v v <--------' | (q3)-----a---->((q4))------------' <----T----- b) Teste a sentença "aaaba" - computação do autômato (q0,aaaba) |- (q1,aaaba) |- (q2,aaba) |- (q2,aaba) |- (q2,aba) |- |- (q2,ba) |- (q4,a) |- (q3,a) |- (q4,T) - conclusão - q4 E F - a sentença "aaaba" é aceita pelo AFN * Eliminação de Indeterminismos (AFN --> AFD) - transições em vazio - é possível transitar de p para q sem consumir símbolo de entrada - portanto, substituem-se os dois estados por um único - exemplo -----d1---->(q1) -->(p)-----T---->(q)-----d2---->(q2) | ... '-----dn---->(qn) - mais de uma transição - um AFN com |Q| estados pode produzir um AFD equivalente com até 2^|Q| estados - na maioria dos casos, o número de estados do AFD resultante é bem menor - muitos estados criados no AFD equivalente são supérfluos e podem ser unificados com outros estados usando um algoritmo de minimização - exemplo -----d---->(q1) -->(p)-----d---->(q2) | ... '-----d---->(qn) - utilizando a tabela de conversão - criam-se novos estados - para cada unificação de transições em vazio - para cada transição múltipla para o mesmo símbolo - o estado inicial do AFD é o mesmo do AFN - ou é o novo estado que unificou o estado inicial do AFN - todos os estados que unificaram algum estado final original do AFN é um estado final do AFD - exemplo 1) Transforme o AFN em AFD a) AFN c) AFD x y x y |¯v |¯v |¯v |¯v -->(A)-----T---->((B)) -->((D))<----x-----((E)) | ^ ^ | | ^ ^ | | | | | | | y x y y y x y | '---- -----' | | '---- | '----->(C)<------' '----->(C)-------' |_^ y b) Tabela de Conversão --------------------------------- | estado | x | y | T | --------------------------------- | {A} | {A} | {C} | {B} | | {B} | {B} | {C} | --- | | {C} | {A} | {B,C} | --- | | D = {A,B} | {A,B} | {C} | --- | | E = {B,C} | {A,B} | {B,C} | --- | --------------------------------- * Gramática --> AFN - dada uma gramática regular, pode-se construir um AFN que aceite sua linguagem diretamente das regras de produção - exemplo 1) Dada a gramática regular G, construa o AFN que aceite sua linguagem a) G = (V,T,P,S) = (não-terminais, terminais, regra de produção, símbolo inicial) G = ({S,B}, {0,1}, P, S) P = {S --> 0B, B --> 0B, B --> 1S, B --> 0 } b) Função de Transição d(S,0) = {B} // S --> OB d(B,0) = {B,A} // B --> OB, B --> 0 (A é estado final) d(B,1) = {S} // B --> 1S c) AFN 0 |¯¯¯v -->(S)-----0---->({A,B})-----0---->((A)) <----1----- d) Tabela de Equivalência ------------------------ | regra | transição | ------------------------ | A --> T | d(A,T) = qf | | A --> a | d(A,a) = qf | | A --> B | d(A,T) = B | | A --> aB | d(A,a) = B | ------------------------ e) AFN Simplificado (visualmente / intuitivamente) 0 |¯v -->(S)-----0---->((B)) <----1----- * AFN --> Gramática - da mesma forma com que podemos construir um autômato a partir de uma gramática regular, uma gramática regular pode ser facilmente escrita a partir de um autômato - se o autômato contiver transições para estados de erros (estados de onde não é possível aceitar a sentença, as regras correspondentes não devem ser escritas porque elas não devem gerar sentenças - se forem escritas elas podem gerar loops na gramática - exemplo 1) Dado o AFN, construa a Gramática Regular que gera esse AFN a) AFN 0 |¯v -->(S)-----0---->((B)) <----1----- b) Gramática S --> OB // d(S,0) = B (lê-se: delta, estando em S, consumindo 0, resulta em B) B --> 1S // d(B,1) = S B --> OB // d(B,0) = B B --> O // B é estado final 2) Construa uma gramática que gera todas as sentenças sobre {a,b,c}* sem que haja símbolos iguais consecutivos - como a sentença vazia pertençe à linguagem, deve haver uma regra S --> T - algumas sentenças começam com a (óbvio), que pode ser seguido por qualquer subsentença da linguagem que não comece com a - o mesmo raciocínio aplica-se a "b" e "c" S --> aA | bB | cC - a variável A pode ser vazia ou qualquer subsentença que começa com b ou com c - se começar com b, deve ser seguido por uma subsentença, talvez vazia, que não comece com b, que é a variável B - o mesmo ocorre com começo c - raciocínio semelhante aplicado a B e C leva a A --> bB | cC | T B --> aA | cC | T C --> aA | bB | T a) Gramática G = (V,T,P,S) = (não-terminais, terminais, regra de produção, símbolo inicial) V = {S,A,B,C} T = {a,b,c} P = {S --> aA | bB | cC | T A --> bB | cC | T B --> aA | cC | T C --> aA | bB | T } b) AFN ------. ,--------------a-------------->((A))<-. | | ^ | | | | | | | | | a b | | | -------------' / | | -->(S)-----b---->((B))<-------------- a c | -------------. \ | | | c b | | | | | | | | v | | | '--------------b-------------->((C))--' | <-----' * ER --> AFN - ER descrevem linguagens regulares - é possível então - para qualquer ER, construir um AFN que aceita a linguagem descrita pela ER (fácil) - para qualquer AFN, construir uma ER que descreve a linguagem aceita pelo AFN (difícil) - para qualquer x pertence E, a expressão x denota a linguagem {x}, portanto -->(A)-----x---->((B)) - a expressão T corresponde a -->(A)-----T---->((B)) - os parênteses não corresopndem a nada especificamente - um AFN que representa a ER (r1) é o mesmo que representa r1 - a idéia não é construir o melhor autômato (menos estados), mas sim mostrar que existe um AFN equivalente, que pode ser construído por um algoritmo - concatenação - a concatenação pode ser simplesmente representada pelo encadeamento de AFN's - um novo estado inicial é construído na frente do 1º AFN e um novo estado final é construído após o 2º AFN - AFN para r1 . r2 M(r1) M(r2) ,----------------------. ,----------------------. | | | | -->( )-----T--|-->( )--´\/\/\,->( )--|--T--|-->( )--´\/\/\,->( )--|--T-----(( )) | | | | '----------------------' '----------------------' - união - a união representa uma escolha - AFN para r1 | r2 M(r1) ,----------------------. | | ,-----T--|-->( )--´\/\/\,->( )--|--T-----. | | | | | '----------------------' | | v -->( ) (( )) | M(r2) ^ | ,----------------------. | | | | | '-----T--|-->( )--´\/\/\,->( )--|--T-----' | | '----------------------' - repetição - zero ou mais vezes - AFN para r1* ,---------------------T---------------------. | | | M(r1) | | ,----------------------. | | | | v -->( )-----T--|-->( )--´\/\/\,->( )--|--T---->(( )) | | | ^ | '----------------------' | | | | | '---------------------T---------------------' * AFN --> ER - a construção de uma ER a partir de um autômato não é tão trivial quanto a tarefa inversa, pois um AFN pode ter ciclos e loops arbitrários - a estratégia básica é a seguinte - se o AFN tiver mais de um estado final, converta-o para um AFN com um único estado final - para isso, transforme os estados finais em não-finais e adicione uma transição em vazio de cada um destes antigos estados finais até o novo estado final criado - exemplo -->(( )) -->((A)) | | | | v v -->(( )) ==> -->((B))-----T---->(( )) ^ ^ | | | | -->(( )) -->((C)) VOLTAR PRA PÁGINA 71 E 72!!! * Algoritmo de Minimização (número de estados) - requisitos - autômato tem que ser determinístico (AFD) - não pode ter estados inalcançáveis a partir do estado inicial - exemplo de estados inalcançáveis que devem ser removidos antes da execução do algoritmo <----a----- -->((1))-----a---->(2)-----b---->((3))<----b-----(8) - os estados ^ | | ^ | ^ | 7 e 8 são | | | | | | | inalcançáveis a b a a b b a a partir do | | | | | | | estado 1 | v v | v | v (4)-------b---->(5)<----b-----(6)<------a-----(7) |_^ a,b - o conjunto de estados alcançáveis pode ser computado assim R <-- {q0} enquanto existir estado p pertence R e a pertence E : d(p,a) !pertence R R <-- R U {d(p,a)} - exemplo de AFD com estados inalcançáveis removidos (pode ser minimizado com o algoritmo) <----a----- -->((1))-----a---->(2)-----b---->((3)) R <-- {1} ^ | | ^ | R <-- {1,2} | | | | | R <-- {1,2,4} a b a a b R <-- {1,2,4,5} | | | | | R <-- {1,2,3,4,5} | v v | v R <-- {1,2,3,4,5,6} (4)-------b---->(5)<----b-----(6)< |_^ a,b * Algoritmo de Minimização (4 passos) - construa uma tabela relacionando os estados distintos, onde cada par aparece apenas uma vez - marque todos os pares constituídos de um estado final e outro não-final - para cada par {qu,qv} não marcado para cada símbolo a pertence E - calcule d(qu,a) = pu d(qv,a) = pv - se pu == pv, não faça nada - se pu != pv e o par {pu,pv} não estiver marcado, adicione {qu,qv} a uma lista encabeçada por {pu,pv} para análise posterior - se pu != pv e o par {pu,pv} estiver marcado - marque {qu,qv} - se {qu,qv} encabeçar alguma lista, marque todos os pares desta lista e, recursivamente, se algum par da lista encabeçar outra lista - os estados dos pares não marcados são equivalentes e podem ser unificados - um estado unificado deve ser inicial se um de seus componentes originais era inicial - as transições do par unificado são a união das transições dos dois estados originais - a equivalência de estados (pares não marcados) é transitiva - se {a,b} e {b,c} são equivalentes, então {a,c} são equivalentes - observação - por construção, somente dois estados do mesmo tipo, final ou não-final, são declarados equivalentes - quando se analisa um par e a primeira transição resulta na marcação deste par, podem-se ignorar as análises das outras transições relativas a este par - no entanto, se essas análises forem feitas, não causam problemas (apenas é um trabalho desnecessário) - exemplo 1) a) AFD <----a----- -->((1))-----a---->(2)-----b---->((3)) ^ | | ^ | | | | | | a b a a b | | | | | | v v | v (4)-------b---->(5)<----b-----(6)< |_^ a,b b) Tabela X = não são equivalentes .-------. - após os dois primeiros passos do | 2 | X | algoritmo, os pares marcados '-----------. não são equivalentes | 3 | | X | '---------------. - os pares não marcados podem ser | 4 | X | | X | equivalentes, mas ainda não temos '-------------------. certeza | 5 | X | | X | | '-----------------------. | 6 | X | | X | | | '-----------------------' | 1 | 2 | 3 | 4 | 5 | '-------------------' c) Análise dos Pares Não Marcados par {1,3} d(1,a) = 2 não faz d(3,a) = 2 nada d(1,b) = 4 o par {4,6} não está marcado ==> adicionar {1,3) d(3,b) = 6 à lista encabeçada por {4,6} par {2,4} d(2,a) = 5 {1,5} está marcado ==> marca {2,4} e verifica lista d(4,a) = 1 encabeçada por {2,4} (vazia) d(2,b) = 3 {3,5} está marcado, mas esta análise é desnecessária d(4,b) = 5 porque {2,4} já foi marcado na análise anterior (acima) par {2,5} d(2,a) = 5 não faz d(5,a) = 5 nada d(2,b) = 3 {3,5} está marcado ==> marca {2,5} e verifica lista d(5,b) = 5 encabeçada por {2,5} (vazia) par {2,6) d(2,a) = 5 (3,5) está marcado ==> marca {2,6} e verifica lista d(6,a) = 3 encabeçada por {2,6} (vazia) d(2,b) = 3 idem d(6,b) = 5 par {4,5} d(4,a) = 1 {1,5} está marcado ==> marca {4,5} e verifica lista d(5,a) = 5 encabeçada por {4,5} (vazia) d(4,b) = 5 não faz d(5,b) = 5 nada par {4,6} d(4,a) = 1 {1,3} não está marcado ==> adicionar {4,6} d(6,a) = 3 à lista encabeçada por {1,3} d(4,b) = 5 não faz d(6,b) = 5 nada par {5,6} d(5,a) = 5 {3,5} está marcado ==> marca {5,6} e verifica lista d(6,a) = 3 encabeçada por {5,6} (vazia) d(5,b) = 5 já foi verificado d(6,b) = 6 na análise anterior d) Tabela após este passo .-------. - após este passo, o exemplo mostra | 2 | X | que dois pares (identificados por .), '-----------. {1,3} e {4,6} são equivalentes e | 3 | . | X | podem ser unificados '---------------. | 4 | X | x | X | - novas marcações foram feitas '-------------------. com x | 5 | X | x | X | x | '-----------------------. - marcações originais foram feitas | 6 | X | x | X | . | x | com X '-----------------------' | 1 | 2 | 3 | 4 | 5 | '-------------------' e) Estado das Listas --------------- | {4,6} | {1,3} | --------------- | {1,3} | {4,6} | --------------- f) Unificação dos Pares Não Marcados - o último passo do algoritmo consiste na unificação destes dois pares não-marcados - olhando o diagrama de estados do AFD pode-se ver que fazemos uma rotação dos estados 3 e 6 em torno da aresta que une os estados 2 e 5 até fazê-los coincidir com os estados 1 e 4, respectivamente - AFD resultante da unificação dos pares não marcados <----b----- -->((13))-----a---->(2) ^ | | | | | a b a | | | | v v (46)------b---->(5) |_^ a,b * Resumo - uma gramática regular gera uma linguagem regular, ou seja, produz todas as sentenças de uma linguagem regular - uma expressão regular é outra forma de expressar uma linguagem regular - uma expressão regular também produz todas as sentenças de uma linguagem regular - um AFD ou AFI aceita as palavras de uma linguagem regular - uma linguagem é regular se e somente se for possível construir um autômato finito que a aceite - uma linguagem é regular se e somente se for possível expressá-la por uma gramática regular - uma linguagem é regular se e somente se for possível expressá-la por uma expressão regular - a classe das linguagens regulares é fechada para as operações - união - concatenação - intersecção - complemento * GLD --> AFN - GLD = Gramática Linear à Direita - AFN = Autômato Finito Não Determinístico - qualquer AFN tem um AFD equivalente, ou seja, que aceita a mesma linguagem - geralmente, o algoritmo de conversão AFN --> AFD cria estados equivalentes que podem ser verificados através de um algoritmo de minimização de estados - exemplo ----------------------------------------------------------------- | GLD | AFN | ----------------------------------------------------------------- | | | | A --> xB | (A)-----x---->(B) | | A --> xyzB | (A)-----x----->( )-----y---->( )-----z---->(B) | | A --> B | (A)-----T----->(B) | | A --> x | (A)-----x----->(( )) | | A --> T | (A)-----T----->(( )) | | | | ----------------------------------------------------------------- * Gramáticas Livres de Contexto (GLC) (tipo 2) - são gramáticas, definidas usualmente como G = (V,T,P,S) = (não-terminais, terminais, regra de produção, símbolo inicial) - com restrições menos proibitivas que as Gramáticas Regulares (GR) - ou seja, uma GLC é mais ampla que uma GR - as regras de produção de uma GLC são da forma A --> a A pertence V a pertence (V união T)* - OBS: neste caso, T = letra t maiúscula, não lâmbda - em outras palavras, o lado esquerdo de qualquer regra compõe-se de uma única variável (como nas GR) e o lado direito é qualquer combinação de terminais e não-terminais - uma linguagem é livre de contexto (LLC) se for gerada por uma GLC - por definição, toda GR também é GLC - mas nem toda GLC é GR - GLC --> ampla, genérica - GR --> restrita - estas linguagens mais genéricas que as regulares conseguem expressar - parênteses balanceados - blocos estruturados - outras construções típicas de linguagens de programação - os algoritmos são relativamente simples e incluem, por exemplo, analisadores sintáticos, processadores de texto, etc... - o nome "livre de contexto" vem da possibilidade de substituir um não-terminal independentemente do contexto onde ele aparece - esta substituição é sempre possível porque os não-terminais aparecem sozinhos no lado esquerdo das regras - exemplo 1) a) Gramática G = (V,T,P,S) = (não-terminais, terminais, regra de produção, símbolo inicial) G = ({S}, {a,b}, {S --> aSb, S --> T}, S) b) Funcionamento S --> aSb --> aaSbb --> aaaSbbb --> aaabbb c) Linguagem L(G) = {a^n b^n : n >= 0} d) Para que a linguagem fosse L(G) = {a^n b^n : n > 0} - bastaria substituir a regra S --> T por S --> ab 2) Gramática que gera sentenças com parênteses equilibrados G = ({S}, {(,)}, {S --> SS, S --> (S), S --> T}, S) 3) Dada a gramática livre de contexto G, determine a linguagem L(G) gerada por G a) Gramática G = ({S,A,B}, {0,1}, P, S) P = {S --> AB A --> 0A11 | T B --> 0B | T } b) Linguagem L(G) = {0^n 1^2n 0^m : n >= 0, m >= 0} 4) Gramática para números naturais sem zeros à esquerda G = ({N,P,R,D}, {0,1,2,3,4,5,6,7,8,9}, P, N) P = {N --> PR | 0 R --> DR | D D --> 0 | P P --> 1|2|3|4|5|6|7|8|9 } 5) Determinte a linguagem gerada pela gramática G a) Gramática G = ({S,A}, {0,1}, {S --> S0, S --> A1, A --> 0A0, A --> 1}, S) b) Funcionamento S --> S0 --> S00 --> S000 --> A1000 --> 0A01000 --> 00A001000 --> 000A0001000 --> 00010001000 c) Linguagem L(G) = {0^n 1 0^n 1 0^m : n >= 0, m >= 0} d) Gramática Equivalente - uma gramática equivalente pode ser constituída considerando que a linguagem {0^n 1 0^n 1 0^m} é a concatenação das linguagens {0^n 1 0^n} e {1 0^m} G = ({S,A,B}, {0,1}, {S --> AB, A --> 0A0 | 1, B --> B0 | 1}, S) - as regras de A geram {0^n 1 0^n} - as regras de B geram {1 0^m} - a regra de S concatena A e B * Árvores Sintáticas - considere a GLC G = ({E}, {+,*,(,),a}, P, E) P = {E --> E + E E --> E * E E --> (E) E --> a } - a sentença (a + a) * a pode ser derivada assim E --> E * E --> (E) * E --> (E + E) * E --> (a + E) * E --> (a + a) * E --> (a + a) * a - é conveniente para os algoritmos representar a derivação de sentenças de LLC's através de uma árvore sintática de derivação - funcionamento - a raiz é o símbolo inicial da gramática - os nós internos são não-terminais - uma regra A --> X1 X2 ... Xn é representada por uma subárvore com A na raiz e filhos X1, X2, ..., Xn - as folhas (nós sem filhos) são símbolos terminais - as sentenças são lidas da esquerda para a direita - chama-se derivação mais à esquerda à seqüência de produção aplicada sempre ao não-terminal mais à esquerda da forma sentencial produzida até o momento - de forma semelhante, define-se derivação mais à direita - diz-se que há ambigüidade quando uma mesma sentença possui árvores sintáticas diferentes para a mesma sentença usando derivações mais à esquerda ou mais à direita - a ambigüidade é uma característica indesejável de uma gramática, pois pode alterar a semântica de uma mesma sentença - no caso de um compilador, por exemplo, ele poderia calcular valores diferentes para uma mesma expressão aritmética ou emparelhar "else" com "then" de maneiras diferentes - exemplo 1) Sentenças da linguagem gerada pela gramática G a) Gramática G = ({E}, {+,*,(,),a}, P, E) P = {E --> E + E E --> E * E E --> (E) E --> a } b) Árvore --> (a + a) * a c) Árvore --> a + (a * a) E E /|\ /|\ .--´ | `--. .--´ | `--. / | \ / | \ / | \ / | \ E * E E + E /|\ | | /|\ .--´ | `--. | | .--´ | `--. / | \ | | / | \ / | \ | | / | \ ( E ) a a ( E ) /|\ /|\ .--´ | `--. .--´ | `--. / | \ / | \ / | \ / | \ a + a a * a c) Ambigüidade - podemos gerar a sentença a + a * a de várias maneiras E --> E + E --> a + E --> a + E * E --> a + a * E --> a + a * a E --> E + E --> E + E * E --> E + E * a --> E + a * a --> a + a * a E --> E + E --> E + E * E --> a + E * E --> a + a * E 2) Usando a GLC do exemplo anterior e derivações mais à esquerda a) Sentença 1 E --> E + E --> a + E --> a + E * E --> a + a * E --> a + a * a b) Sentença 2 E --> E * E --> E + E * E --> a + E * E --> a + a * E --> a + a * a c) Árvore 1 d) Árvore 2 E E /|\ /|\ .--´ | `--. .--´ | `--. / | \ / | \ / | \ / | \ E + E E * E | /|\ /|\ | | .--´ | `--. .--´ | `--. | | / | \ / | \ | | / | \ / | \ | a E * E E + E a | | | | | | | | a a a a (* tem precedência sobre +) (+ tem precedência sobre *) d) Gramática que resolve este problema G = ({E,T,F}, {+,*,(,)}, P, E) P = {E --> T E --> E + T T --> F T --> T * F F --> (E) F --> a } e) Árvore Sintática da sentença a + a * a E --> E + T --> T + T --> F + T --> a + T --> a + T * F --> a + F * F --> a + a * F --> a + a * a E /|\ .--´ | `--. / | \ / | \ E + T | /|\ | .--´ | `--. | / | \ | / | \ T T * F | | | | | | F F a | | | | a a - nota-se que nesta gramática o operador * tem precedência sobre o operador + f) Árvore Sintática da sentença a * (a + a) E | | T /|\ .--´ | `--. / | \ / | \ T * F | /|\ | .--´ | `--. | / | \ | / | \ F ( E ) | /|\ | .--´ | `--. | / | \ | / | \ a E + E | | T T | | F F | | a a - se for necessário somar (+) antes da multiplicação, a gramática gera parênteses para alterar a precedência implícita dos dois operadores * Autômato com Pilha (AFP) - para simular regras do tipo A --> xBy, podemos considerar A e B como estados e transitar de A para B consumindo x e empilhando y para futura comparação com os símbolos da sentença de entrada - a operação de empilhamento é adequada para levar em conta regras do tipo B --> uCv, já que no processamento deste tipo de regra, v deve ser empilhado para ser comparado (usado) antes de y, porque B é processado antes (A --> xBy) - o dispositivo AFP é semelhante a um autômato finito, mas tem uma pilha como memória auxiliar para acomodar as características das LLC's, conforme descrito acima - "assim os últimos serão os primeiros, e os primeiros serão os últimos" (Matheus, 20:16) * Reconhecedores de LLC's - as LLC's exigem algo mais que um autômato finito para seu reconhecimento - é necessária uma mamória auxiliar para o registro dos fatos de parte já consumida da sentença de entrada - não-determinismos também são convenientes para facilitar o emprego da informação anteriormente memorizada durante o processo de reconhecimento - um autômato para o reconhecimento de LLC's deve inspirar-se nas GLC's - o dispositivo reconhecedor de tais linguagens é o autômato com pilha (push-down automata) * Formalismo dos AFP's - teorema - toda LLC é aceita por algum AFP - toda linguagem aceita por um AFP e livre é uma LLC - dada uma LLC, há um AFP com, no máximo, três estados, que aceita a linguagem - embora não seja possível garantir que um AFP pára (transições em vazio), há um AFP que pára para qualquer LLC - definição formal de AFP - um AFP é uma sêxtupla - M = (Q,E,V,d,q0,F) = (estados, alfabeto de entrada, alfabeto da pilha, função de transição, estado inicial, estados finais) - Q = AFD - E = AFD - V - alfabeto finito de símbolos da pilha - embora V = E em muitos casos, o formalismo dá a liberdade de empilhar/desempilhar símbolos diferentes dos da sentença analisada - d - delta minúscula - função de transição - d : Q . (E união {T}) . V --> 2 ^ ((Q . V)*) - q0 = AFD - F = AFD * Transições e Configurações - AFP - a linguagem aceita por um AFP M pode ser formalmente descrita assim - M = (Q,E,V,d,q0,F) = (estados, alfabeto de entrada, alfabeto da pilha, função de transição, estado inicial, estados finais) - L(M) = {w : (q0,w,T) |-* (p,T,T) : p E F} - se na última configuração temos (estado_final,T,T), então a sentença é aceita, pois - encerrou num estado final - não há mais símbolos do alfabeto de entrada para consumir (alfabeto da pilha está vazio) - não há mais símbolos do alfabeto da pilha para consumir (pilha está vazia) - exemplo 1) d(p,a,z) = {(q1,a1), (q2,a2), ..., (qn,an)} - p, qi pertence Q - a pertence E - Z pertence V - ai pertence V* - esta transição indica que - no estado p - consome símbolo a da entrada - desempilha z - transita para um dos possíveis estados qi (não determinístico) - empilhando a sentença a do alfabeto da pilha 2) d(p,T,z) = {(q,T)} - esta transição indica que - no estado p - não consome símbolo de entrada - desempilha z - transita para q - não empilha nada 3) Descrever a configuração de um AFP num determinado instante - listar o conteúdo da pilha (p,aw,zA) |- (q,w,BA) se d(p,a,z) = (q,B) - esta transição indica que - no estado p - com a subsentença aw - com conteúdo de pilha zA (z no topo) - pode-se transitar para o estado q - consumindo a - conteúdo de pilha BA (desempilhou z e empilhou B) - lê-se - delta - estando em p - consumindo a - desempilha z - transita para q - empilha B * Diagramas de Estado - AFP - embora haja outros funcionamentos (todos equivalentes), um AFP funciona assim - o estado inicial da pilha é vazio - o AFP transita - a partir do estado inicial - para outros estados (não-determinístico) - consumindo símbolos da entrada (ou vazio) - e consumindo símbolos da pilha (ou vazio) - se um dos possíveis estados atingidos após o consumo da sentença for final e a pilha estiver vazia - aceita a sentença - senão - rejeita a sentença - exemplo 1) a) Linguagem L(M) = {w c w^r : w pertence {a,b}*} OBS: w^r = reversa de w b) M = ({q0,q1}, {a,b,c}, {a,b}, d, q0, {q1}) d(q0,a,T) = {(q0,a)} - lê-se - estando em q0 - consome a - sem desempilhar - transita para q0 - empilha a d(q0,b,T) = {(q0,b)} - lê-se - estando em q0 - consome b - sem desempilhar - transita para q0 - empilha b d(q0,c,T) = {(q1,T)} - lê-se - estando em q0 - consome c - sem desempilhar - transita para q1 - sem empilhar d(q1,a,a) = {(q1,T)} - lê-se - estando em q1 - consome a - desempilha a - transita para q1 - sem empilhar d(q1,b,b) = {(q1,T)} - lê-se - estando em q1 - consome b - desempilha b - transita para q1 - sem empilhar c) AFP a[v a] a[^ a] |¯¯v |¯¯v -->(q0)-----c---->((q1)) |__^ |__^ b[v b] b[^ b] d) Linguagem - L(M) aceita palíndromos ímpares e) Teste a sentença "abacaba" (q0,abacaba,T) |- (q0,bacaba,a) |- (q0,acaba,ba) |- (q0,caba,aba) |- (q1,aba,aba) |- (q1,ba,ba) |- (q1,a,a) |- (q1,T,T) - portanto, a linguagem reconhecida pelo AFP M é L(M) = aceita palíndromos ímpares 2) a) Linguagem L(M) = {w pertence {a,b}* : w com mesmo número de a's e b's} b) M = ({q0,q1,q2}, {a,b}, {a,b,c}, d, q0, {q2}) d(qo,T,T) = {(q1,c)} d(q1,a,c) = {(q1,ac)} d(q1,a,a) = {(q1,aa)} d(q1,a,b) = {(q1,T)} d(q1,b,c) = {(q1,bc)} d(q1,b,b) = {(q1,bb)} d(q1,b,a) = {(q1,T)} d(q1,T,c) = {(q2,T)} c) AFP -->(q0)-----T[vc]---->(q1)-----T[^c]---->((q2)) |__^ a[^b] a[^a vaa] a[^c vac] b[^a] b[^b vbb] b[^c vbc] d) Linguagem - L(M) aceita sentenças com mesmo número de a's e b's e) Teste a sentença "abba" (q0,abba,T) |- (q1,abba,c) |- (q1,bba,ac) |- (q1,ba,c) |- (q1,a,bc) |- (q1,T,c) |- (q2,T,T) - portanto, a linguagem reconhecida pelo AFP M é L(M) = aceita sentenças com mesmo número de a's e b's * Gramáticas Sensíveis a Contexto (GSC) (tipo 1) - relaxando as regras das GLC's a ponto de permitir que o lado esquerdo possa conter uma forma sentencial em vez de um único não-terminal, temos uma gramática mais ampla - para distinguir estas gramáticas das mais genéricas (tipo 0), há uma restrição - nenhuma substituição pode reduzir o tamanho da forma sentencial a que a substituição foi aplicada - isso significa que as regras das GSC's são do seguinte tipo aAb --> ayb - a,b pertence (V união T)* - A pertence V - y pertence (V união T)+ - como A é substituído por y, que não pode ser vazio, o tamanho do lado direito não é menor que o esquerdo - o nome "sensível a contexto" vem da permissão de substituição de A apenas quando ele aparece no contexto aAb, ou seja, depois de a e antes de b - exemplo 1) Aceita números naturais sem zeros à esquerda a) Linguagem L(G) aceita números naturais sem zeros à esquerda b) Gramática G = ({N,D}, {0,1,2,3,4,5,6,7,8,9}, P, N) P = {N --> ND | D ND --> 1D | 2D | 3D | 4D | 5D | 6D | 7D | 8D | 9D D --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 } 2) a^n b^n c^n a) Linguagem L(G) = {a^n b^n c^n : n > 0} b) Gramática G = ({S,B,C}, {a,b,c}, P, S) P = {S --> aSBC S --> aBC CB --> BC aB --> ab bB --> bb bC --> bc cC --> cc } c) Teste a derivação de a^4 b^4 c^4 S --> aSBC --> aaSBCBC --> aaaSBCBCBC --> aaaaBCBCBCBC --> aaaaBBCBCBCC --> aaaaBBCBCBCC --> aaaaBBBCBCCC --> aaaaBBBBCCCC --> aaaabBBBCCCC --> aaaabbBBCCCC --> aaaabbbBCCCC --> aaaabbbbCCCC --> aaaabbbbcCCC --> aaaabbbbccCC --> aaaabbbbcccC --> aaaabbbbcccc * Gramáticas com Estrutura de Frase (GEF)(tipo 0) - são aquelas sem quaisquer restrições às suas regras de produção - portanto, estas regras são do tipo a --> b a pertence (V* união T+) b pertence (V união T )* - as linguagens geradas por estas gramáticas são conhecidas como linguagens enumeráveis recursivamente, ou linguagens tipo 0 * Reconhecedores - as LSC são reconhecidas por autômatos adaptativos (alteram-se dinamicamente), ou por Máquinas de Turing - as linguagens enumeráveis recursivamente são reconhecidas por Máquinas de Turing - existem linguagens não-enumeráveis recursivamente, que não podem ser reconhecidas por nenhum dispositivo algorítmico - o modelo de Chomsky foi definido para o estudo de linguagens naturais - no caso de linguagens naturais, o estudo das LLC tem sido de especial interesse, pois ela permite uma representação simples da sintaxe, adequada tanto para a estruturação formal, como para a análise computacional - mas há problemas não-solucionáveis... - quanto às linguagens de programação, as LR e LLC são usadas em muitas partes sem estudo e análise - no entanto, há aspectos que não conseguem ser tratados pelas LLC, como declarações e uso de identificadores - a hierarquia de Chomsky nem sempre é adequada para as linguagens de programação - há casos em que as LLC não são suficientes, mas as LSC são excessivas - em outros casos, as LLC são excessivas, mas as LR são insuficientes - o campo é vasto e existem muitos problemas não solucionados... * Autômato Adaptativo - cria o autômato em tempo de execução - reconhece uma LLC sem pilha - o Autômato Adaptativo é um reconhecedor de LLC e LSC - a Máquina de Turing é um reconhecedor das LRE (Linguagens Recursivamente Enumeráveis) - toda LR é LLC - exemplo 1) a) Linguagem LLC: {a^n b^n : n > 0} b) Autômato -->( ) (( )) | ^ | | a b | | v | ( )---T--->(( )) | ^ | | a b | | v | ( )---T--->(( )) | ^ | | a b | | v | ( )---T--->(( )) * Máquina de Turing (MT) - é um modelo matemático simples de um computador - apesar de sua simplicidade, seu poder de computação não é menor do que qualquer outro dispositivo, por mais complexo que possa ser - esta simplicidade é útil, pois elimina muitos detalhes supérfluos na demonstração de teoremas e no estudo de algoritmos - o matemático David Hilbert quis encontrar um algoritmo para determinar a veracidade ou falsidade de qualquer proposição matemática - no entanto, Kurt Gödel publicou seu famoso teorema da incompletude em 1931, que demonstrou que tal algoritmo não pode existir - ele construiu uma proposição cuja definição mostrava que ela não podia ser nem provada nem rejeitada dentro do mesmo sistema lógico onde a proposição fora feita - esta conclusão pode ser considerada como uma das grandes conquistas intelectuais do século XX - baseado no pensamento de Gödel, o conceito de procedimento efetivo ou algoritmo foi formalizado e verificado que não existem algoritmos para computar muitos problemas - atualmente, a MT é aceita como a formalização de algoritmo - não é possível provar que uma MT é equivalente a nossa noção intuitiva de um computador, mas há argumentos fortes para esta equivalência - esta é a chamada hipótese de Church - "a capacidade de computação representada pela MT é o limite máximo que pode ser atingido por qualquer dispositivo de computação" - com esta hipótese, prova-se, por exemplo, o teorema de Bshm-Jacopini - "qualquer problema que tenha solução pode ser resolvido com apenas três estruturas básicas de controle: seqüência, seleção, iteração" * Modelo de MT - este modelo consiste de - um controle de estados finitos - uma fita que pode ser lida e gravada - um cabeçote capaz de mover para a esquerda e direita - responsável pela comunicação entre a fita e o cabeçote - a fita é dividida em células, cada uma capaz de armazenar um símbolo, mas é infinita em ambas as direções com um símbolo especial (branco), normalmente denotado por #, como símbolo de fundo - ou seja, assume-se que todas as células da fita contêm brancos exceto aquelas ocupadas pela sentença de entrada - graficamente, podemos representar a MT assim ___________________________________________ |...| # | a1| a2|...| ai|...| an| # | # |...| ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯^¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ | p - a máquina está no estado p com o cabeçote apontando para o símbolo ai - a unidade de controle opera em passos discretos - em cada passo, ela realiza quatro funções, que dependem do seu estado e do símbolo da fita que está na célula apontada pelo cabeçote - passos - 1) lê o símbolo corrente da fita - 2) grava um novo símbolo, substituindo o símbolo lido - 3) move o cabeçote para a célula da direita ou da esquerda - 4) transita para um novo estado - a MT é alimentada com uma sentença e o cabeçote é posicionado no primeiro símbolo desta sentença, com o controle assumindo o estado inicial - a MT transita de estado em estado de acordo com uma relação de transição, alterando a fita neste processo, e aceitando a sentença no momento em que atingir um estado final - a MT é definida como uma séptupla - M = (Q,E,V,d,q0,F,B) = (estados, alfabeto entrada, alfabeto auxiliar, relação de transição, estado inicial, estados finais, símbolo branco) - Q = AFD - E = AFD - V - alfabeto auxiliar - d - delta minúsculo - relação de transição - d : (Q - F) . (E união V) --> Q . (E união V) . {E,D} - E --> esquerda (cabeçote) - D --> direita (cabeçote) - q0 = AFD - F = AFD - B - símbolo branco (B pertence V) - a relação de transição d mapeia uma dupla (estado atual, símbolo de entrada ou auxiliar) numa trinca (novo estado, símbolo de entrada auxiliar, direção do cabeçote) - a relação não está definida para os estados finais (por isso, Q - F) - ou seja, a máquina pára e aceita a sentença se um dos estados finais for atingido, independentemente da posição do cabeçote e do conteúdo atual da fita * Transições e Configurações - MT - exemplo 1) d(p,a) = (q,b,D) p pertence Q - F q pertence Q a pertence E união V b pertence E união V - quando M estiver no estado p e ler o símbolo a da fita, grava b, substituindo a, move o cabeçote uma célula à direita, e transita para o estado q 2) d(p,a) = (q,b,E) p pertence Q - F q pertence Q a pertence E união V b pertence E união V - quando M estiver no estado p e ler o símbolo a da fita, grava b, substituindo a, move o cabeçote uma célula à esquerda, e transita para o estado q - como uma MT grava símbolos na fita, uma MT é de fato um transdutor - além de reconhecer sentenças de uma linguagem, a MT também computa funções, com a sentença de entrada como parâmetro e a finta final como resultado da computação - uma configuração de uma MT definida por (p,y1 a y2) p pertence Q y1 pertence (E união V)* y2 pertence (E união V)* a pertence (E união V) - significa - o estado corrente é p - o cabeçote aponta o símbolo a - que é precedido e seguido por outros símbolos do alfabeto total da fita - graficamente ___________ | y1| a | y2| ¯¯¯¯¯^¯¯¯¯¯ | p - se d(p,a1) = (q,b,D) então uma configuração passa para outra configuração] (p,y1 a1 a2 y2) |- (q, y1 b a2 y2) - lê-se - estando em p - lê o símbolo a1 - substitui-o por b - move o cabeçote para a direita - transitando para o estado q - graficamente _______________ _______________ | y1| a1| a2| y2| |- | y1| b | a2| y2| ¯¯¯¯¯^¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯^¯¯¯¯¯ | | p q - exemplo 1) (p,y1 a1 a2 y2) |- (q, y1 a1 b y2) se d(p,a2) = (q,b,E) _______________ _______________ | y1| a1| a2| y2| |- | y1| a1| b| y2| ¯¯¯¯¯¯¯¯¯^¯¯¯¯¯ ¯¯¯¯¯^¯¯¯¯¯¯¯¯¯ | | p q (p,d a) |- (q, wb #) se d(p,a) = (q,b,0) - o movimento de uma célula à direita do último símbolo da fita (ou à esquerda do primeiro) faz o cabeçote apontar um branco (símbolo #) - a fita contém infinitos brancos antes do primeiro símbolo e após o último - estes brancos não são mostrados nas configurações - a linguagem aceita por uma MT M é o conjunto de sentenças em E* que fazem M atingir um estado final à partir do estado inicial com o cabeçote iniciando no primeiro símbolo da sentença L(M) = {w pertence E* : (q0, q) |-* (qf,y) : qf pertence F, y pertence (E união V)* * Diagrama de Estados - MT - definição (p)---a1/a2/s---(q) - p --> estado anterior - a1 --> símbolo lido - a2 --> símbolo gravado - s --> sentido do movimento (E, D) - q --> novo estado - as condições de parada são - 1) a máquina atinge um estado final --> aceita o resultado - 2) a relação de transição é indefinida para o argumento (símbolo e estado corrente) --> rejeita o resultado - a máquina pode entrar em loop infinito - neste caso, a sentença não é aceita nem rejeitada - exemplo 1) Reconhecimento de {a^n b^n : n >= 0} a) Gramática M = (Q,E,V,d,q0,F,B) M = (estados, alfabeto entrada, alfabeto auxiliar, relação de transição, estado inicial, estados finais, símbolo branco) M = ({q0,q1,q2,q3,q4}, {a,b}, {A,B,#}, d, q0, {q4}, #) b) Autômato ,-------------A/A/D-------------------. v | -->(q0)-----a/A/D---->(q1)-----b/B/E---->(q2) | | |_^ |_^ | '---B/B/D---. a/a/D a/a/E #/#/E | B/B/D B/B/E | | v v ((q4))<--#/#/E---(q3) |_^ B/B/D c) Reconhecimento de a^3 b^3 _____________ _____________ _____________ |a|a|a|b|b|b|#| |A|a|a|B|B|B|#| |A|a|a|B|B|B|#| ^¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯^¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯^¯¯¯¯¯¯¯¯ q0 q1 q1 _____________ _____________ _____________ |A|a|a|b|b|b|#| |A|a|a|B|b|b|#| |A|a|a|B|b|b|#| ¯¯¯¯¯¯^¯¯¯¯¯¯ ¯¯¯¯^¯¯¯¯¯¯¯¯ ¯¯^¯¯¯¯¯¯¯¯¯¯ q1 q2 q2 _____________ _____________ _____________ |A|a|a|B|b|b|#| |A|a|a|B|b|b|#| |A|A|a|B|b|b|#| ^¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯^¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯^¯¯¯¯¯¯¯¯ q2 q0 q1 _____________ _____________ _____________ |A|A|a|B|b|b|#| |A|A|a|B|b|b|#| |A|A|a|B|B|b|#| ¯¯¯¯¯¯^¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯^¯¯¯¯ ¯¯¯¯¯¯^¯¯¯¯¯¯ q1 q1 q2 _____________ _____________ _____________ |A|A|a|B|B|b|#| |A|A|A|B|B|b|#| |A|A|a|B|B|b|#| ¯¯¯¯^¯¯¯¯¯¯¯¯ ¯¯^¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯^¯¯¯¯¯¯¯¯ q2 q2 q0 _____________ _____________ _____________ |A|A|A|B|B|b|#| |A|A|A|B|B|b|#| |A|A|A|B|B|b|#| ¯¯¯¯¯¯^¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯^¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯^¯¯ q1 q1 q1 _____________ _____________ _____________ |A|A|A|B|B|B|#| |A|A|A|B|B|B|#| |A|A|A|B|B|B|#| ¯¯¯¯¯¯¯¯^¯¯¯¯ ¯¯¯¯¯¯^¯¯¯¯¯¯ ¯¯¯¯^¯¯¯¯¯¯¯¯ q2 q2 q2 _____________ _____________ _____________ |A|A|A|B|B|B|#| |A|A|A|B|B|B|#| |A|A|A|B|B|B|#| ¯¯¯¯¯¯^¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯^¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯^¯¯ q0 q3 q3 _____________ _____________ |A|A|A|B|B|B|#| |A|A|A|B|B|B|#| ¯¯¯¯¯¯¯¯¯¯¯¯^ ¯¯¯¯¯¯¯¯¯¯^¯¯ q3 q4 - pára, aceitando a palavra!!! d) Funcionamento {a^n b^n : n >= 0} - inicialmente, a fita contém a^n b^n seguida e precedida de uma infinidade de brancos - o cabeçote está no primeiro símbolo - a máquina substitui o símbolo a mais à esquerda por A e move para a direita até o primeiro b, substituindo-o por B - em seguida, move para a esquerda até o A mais à direita, move uma célula à direita até o primeiro a e repete o ciclo - se, ao procurar b, a máquina achar um branco, ela pára, rejeitando a sentença - se, depois de trocar b por B, a máquina não achar nenhum a, ela verifica se não há outro b, aceitando a sentença se não houver - informalmente, cada estado representa uma instrução ou um grupo de instruções de um programa - especificamente, a MT do exemplo {a^n b^n | n > 0} tem o seguinte funcionamento - o estado q0 é o inicial, mas chega-se-lhe também antes de cada substituição de a por A - o estado q1 é usado para pesquisar à direita, pulando os a's e B's até achar um b - se achar um b, troca-o por um B, entrando em q2 - o estado q2 procura um A à esquerda e entra em q0 quando o acha, movendo à direita para o primeiro a quando muda de estado - na pesquisa à direita (no estado q1), se um branco ou A for encontrado antes de um b, a sentença é rejeitada - há muitos a's ou a sentença não é do tipo a* b* - o estado q0 tem outra função - se, após o estado q2 encontrar o A mais à direita, houver um B à sua direita, então os símbolos a esgotaram-se - de q0, pulando B's, vai-se até q3 que pula os B's até encontrar # (verifica se não há outros b's) - ao encontrar o #, entra-se no estado final q4, aceitando a sentença - senão, rejeita a sentença e) Tabela para representar a relação de transição d --------------------------------------------------------------- | estado | a | b | A | B | # | --------------------------------------------------------------- | q0 | (q1,A,D) | | | (q3,B,D) | (q4,#,D) | | q1 | (q1,A,D) | (q2,B,E) | | (q1,B,D) | | | q2 | (q2,a,E) | | (q0,A,D) | (q2,B,E) | | | q3 | | | | (q3,B,D) | (q4,#,D) | | q4 | | | | | | --------------------------------------------------------------- - como a MT produz símbolos de saída na fita, além de reconhecedora de linguagens irrestritas, ela também é um transdutor - a MT é capaz, por exemplo, de computar uma função f: N --> N, pois número natural pode ser representado por uma sentença I^n onde I é um dígito (notação unária) * Outros Exemplos na Apostila - 127 --> somar 1 em um número unário - 128 --> calcular a soma de dois números naturais representados em unário - 129 --> ordenar uma sentença sobre {a,b}* - 130 --> reconhecedor da linguagem {a^n b^n c^n | n >= 0} - 131 --> contador binário (esta máquina não pára; ela incrementa, ininterruptamente, o contador) - 132 --> Extensões da MT - 133 --> MT Universais - 134 --> Conclusões MT * Resumo - Gramáticas (GR, GLC, GSC, GEF) G = (V,T,P,S) = (não-terminais, terminais, regra de produção, símbolo inicial) - AFD M = (Q,E,d,q0,F) = (estados, alfabeto, função de transição, estado inicial, estados finais) - TFD M = (Q,E,G,d,q0) = (estados, alfabeto de entrada, alfabeto de saída, função de transição, estado inicial) - AFN M = (Q,E,d,q0,F) = (estados, alfabeto, função de transição, estado inicial, estados finais) - AFP M = (Q,E,V,d,q0,F) = (estados, alfabeto de entrada, alfabeto da pilha, função de transição, estado inicial, estados finais) - MT M = (Q,E,V,d,q0,F,B) = (estados, alfabeto entrada, alfabeto auxiliar, relação de transição, estado inicial, estados finais, símbolo branco) ----------//----------