Baixe o app para aproveitar ainda mais
Prévia do material em texto
Linguagens Formais e Autômatos – 1º Semestre de 2015 3 - Tipos de Gramáticas Segundo a Hierarquia de Chomsky Uma hierarquia de linguagens de programação baseada no aumento da independência da máquina, possui no seu topo as linguagens orientadas a problemas, ou seja, linguagens que possuem um enfoque voltado a um problema específico e que refletem sua estrutura e sua terminologia. Em seguida, vem a classe de linguagens de alto-nível, a classe mais importante e mais utilizada, composta por estruturas de controle e decisão. Estas linguagens ainda estão próximas das linguagens naturais. Abaixo, estão as linguagens de montagem, que basicamente atribuem mnemônicos as instruções de máquinas da última classe de linguagem, as linguagens de baixo- nível, ou seja, as linguagens nativas dos computadores onde cada instrução é representada por um valor numérico. Das classes da hierarquia baseadas na independência de máquina, vamos nos ater a classe de linguagens de alto-nível, uma vez que é no escopo destas linguagens que os compiladores atuam. De modo geral, pode-se definir as linguagens de alto-nível, as quais de agora em diante serão chamadas simplesmente de linguagens, como uma coleção de cadeia de símbolos, de comprimento finito. Estas cadeias são denominadas sentenças da linguagem e são formadas pela justaposição de elementos individuais, os símbolos ou átomos da linguagem. A teoria de Chomsky nos mostra que existem quatro classes de gramáticas que são capazes de gerar quatro classes de linguagens correspondentes. As quatro classes de gramáticas são: · Gramáticas Irrestritas; · Gramáticas Sensíveis ao Contexto; · Gramáticas Livres de Contexto; · Gramáticas Lineares à Direita (esquerda). Conseguimos atingir estas quatro classes de gramáticas devido às restrições impostas pelas produções desta gramática, conseqüentemente, as linguagens formadas por estas gramáticas também são atingidas. Por este motivo é que dizemos que para cada tipo de gramática existe uma linguagem correspondente. 3.1 - Gramáticas Irrestritas As Gramáticas Irrestritas são as gramáticas formadas sem a imposição de qualquer tipo de 9 Linguagens Formais e Autômatos – 1º Semestre de 2015 restrição por parte das produções, desta forma ela não possui limitação, gerando Linguagem estruturada em frases. Como as gramáticas irrestritas não possuem limitação elas compreendem todas as linguagens que podem se definir através de mecanismos generativos, ou seja, mecanismos que possam ser gerados por estas gramáticas. Segundo a Hierarquia de Chomsky este tipo de gramática é classificado como gramática do tipo 0 e as linguagens que são formadas por este tipo de gramáticas também são correspondentemente linguagens do tipo 0. Exemplo: G=({A,B,C},{a,b},{A→BC, BC→CB, CB→b, B→b, BC→a },A) 3.2 - Gramáticas Sensíveis ao Contexto As Gramáticas Sensíveis ao Contexto são as gramáticas formadas pela imposição de restrição por parte das produções, desta forma as regras de substituições impostas não podem reduzir a forma sentencial à qual a substituição é aplicada, ou seja, a cadeia posterior à substituição tem que possuir um número igual ou maior de símbolos. Segundo a Hierarquia de Chomsky este tipo de gramática é classificado como gramática do tipo 1 e as linguagens que são formadas por este tipo de gramáticas também são correspondentemente linguagens do tipo 1 (Linguagem sensível ao contexto). Desta forma, as linguagens do tipo 1 podem ser geradas através de gramáticas do tipo 0 (Gramáticas Irrestritas), embora o inverso não seja possível. Exemplo: G = ({A,B,C},{a,b},{A→AB, AB→AC, C→abA, B→b,AB→bb, A→a},A) 3.3 - Gramáticas Livres de Contexto As Gramáticas Livres de Contexto são as gramáticas na qual questionamos o condicionamento das substituições, ou seja, levantamos o condicionamento das substituições imposta pelas regras definidas pela produção. Após este questionamento, eliminamos o condicionamento e aplicamos às produções uma restrição adicional, com a finalidade de assim restringirmos as produções das gramáticas deste tipo. Neste tipo de gramática, o lado esquerdo das 10 Linguagens Formais e Autômatos – 1º Semestre de 2015 produções possui apenas um não-terminal. Segundo a Hierarquia de Chomsky este tipo de gramática é classificado como gramática do tipo 2 e as linguagens que são formadas por este tipo de gramáticas também são correspondentemente linguagens do tipo 2 (Linguagem livre de contexto). Desta forma, as linguagens do tipo 2 podem ser geradas através de gramáticas do tipo 1 (Gramáticas Sensíveis ao Contexto) ou gramáticas do tipo 0 (Gramáticas Irrestritas). Exemplo: G=({S},{a,+,*,(,)},{S→S*S,S→S+S, S→(S), S→a}, S) 3.4 - Gramáticas Regulares As Gramáticas Regulares ou Lineares à Direita (Esquerda) são as gramáticas na qual as regras de produção admitem apenas a substituição de um não-terminal por uma cadeia de terminais, seguida ou não por um não-terminal único. Segundo a Hierarquia de Chomsky este tipo de gramática é classificado como gramática do tipo 3 e as linguagens que são formadas por este tipo de gramáticas também são correspondentemente linguagens do tipo 3 (Linguagem Regular ou Linear à Direita). Desta forma, as linguagens do tipo 3 podem ser geradas através de gramáticas do tipo 2 (Gramáticas Livres de Contexto), gramáticas do tipo 1 (Gramáticas Sensíveis ao Contexto) ou gramáticas do tipo 0 (Gramáticas Irrestritas). Exemplo: G=({S},{a,b},{S→aS, S→b }, S) Obs.: Uma Gramática Linear à direita possui produções da forma A→wB ou A→w. Uma Linear à Esquerda, possui produções A→Bw ou A→w. 11 Linguagens Formais e Autômatos – 1º Semestre de 2015 A figura a seguir, disponível em http://pt.wikipedia.org/wiki/Hierarquia_de_Chomsky, apresenta um resumo da Hieraquia de Chomsky. 3.5 - Expressões Regulares Expressão Regular (ER) é uma maneira de descrever conjunto regulares de cadeias. Pode ser considerado também como um gerador, pois a partir da Expressão Regular pode-se gerar as palavras da linguagem. Logo, uma Expressão Regular é um formalismo usado para definir o formato correto de uma cadeia de caracteres (palavras) da Linguagem sobre um alfabeto Para a geração das cadeias são utilizadas as seguintes operações: • Concatenção sucessiva (*) • Concatenção ( . ) • União ( + ) A Concatenação Sucessiva tem precedência sobre a concatenação, a qual tem precedência sobre a união. Considere o alfabeto V = {a, b}. Nele podemos ter as seguintes relações: 12 Linguagens Formais e Autômatos – 1º Semestre de 2015 Expressão Regular Linguagem Representada aa somente a palavra aa ba* todas as palavras que iniciam por b, seguido por zero ou mais a (a + b)* todas as palavras sobre o alfabeto { a, b } (a + b)*aa(a + b)* todas as palavras contendo aa como subpalavra a*ba*ba* todas as palavras contendo exatamente dois b (a + b)*(aa + bb) todas as palavras que terminam com aa ou bb 13 Linguagens Formais e Autômatos – 1º Semestre de 2015 4 – Linguagens Regulares Segundo a Hierarquia de Chomsky, a Linguagem Regular trata-se de uma linguagem mais simples, sendo possível desenvolver algoritmos de reconhecimento ou de geração de pouca complexidade, grande eficiência e de fácil implementação. O estudo das Linguagens Regulares ou tipo 3 (Hierarquia de Chomsky) pode ser visto através de vários formalismos: • Operacional ou reconhecedor - uso dos autômatos finitos (determinístico, não determinístico) • Axiomático ou gerador - gramática regular• Denotacional - expressão regular 4.1 - Reconhecedores Ao contrário das gramáticas, que geram sentenças de uma linguagem, os reconhecedores são dispositivos de aceitação de cadeias, ou seja, realizam um teste de aceitação que determina se uma cadeia pertence ou não a linguagem. Pensando de maneira abstrata, podemos determinar os componentes da estrutura de um reconhecedor de cadeias. São eles: • Uma cadeia de entrada; • Um cursor; e • Uma máquina finita de estados. A máquina finita de estados é o elemento central do funcionamento de um reconhecedor. Trata-se de uma máquina que possui a propriedade de realizar transições a partir de um elemento da cadeia de entrada. Dessa forma, o reconhecimento de uma cadeia transcorre fornecendo o elemento apontado pelo cursor à máquina finita de estados e esta respondendo com o estado resultante da transição. Vale comentar, que eventualmente os eventos ocorridos durante o reconhecimento são registrados em uma memória auxiliar. Em geral, essa memória e representada por uma pilha. Antes de iniciar o processo de reconhecimento, é preciso levar o reconhecedor a uma Linguagens Formais e Autômatos – 1º Semestre de 2015 configuração inicial. Para isso a máquina finita de estados deve também ser levada a sua configuração inicial, além disso o cursor deve apontar para o primeiro elemento da cadeia de entrada. Se a máquina finita de estados possuir memória auxiliar, esta deve conter um valor inicial específico e pré-determinado. A cada instante do reconhecimento, podemos definir uma configuração ao reconhecedor como sendo uma tripla composta pelo estado corrente, pela posição do cursor na cadeia e conteúdo do texto de entrada, e valor da memória auxiliar. Uma cadeia submetida ao processo de reconhecimento é considerada reconhecida, e portanto, pertencente à linguagem definida pelo reconhecedor, se partindo da configuração inicial e passando por todos os elementos da cadeia, o reconhecedor realiza uma seqüência de movimentos que o leve a uma configuração final. Todo reconhecedor deve ter no mínimo uma configuração final, de modo que os movimentos possíveis entre a configuração inicial e uma ou mais configurações finais descrevam as sentenças da linguagem considerada. Podemos então, definir uma configuração final como a situação em que o cursor aponta para uma posição após o último elemento da cadeia, então a máquina de estados encontra-se em um dos estados de aceitação e, se o reconhecedor trabalha com memória auxiliar, o conteúdo da memória satisfaz um critério preestabelecido. 4.1.1 – Formato de Reconhecedores Para a representação de Reconhecedores são utilizadas três notações: • Produções dos autômatos; • Tabelas de Transição; e • Diagramas de Estados. a) Produções dos Autômatos: Um autômato finito M sobre um alfabeto Σ é uma 5-upla (K, Σ, δ, e0, F), onde: • K é um conjunto finito de estados; • Σ é o alfabeto dos símbolos da linguagem; Linguagens Formais e Autômatos – 1º Semestre de 2015 • δ é a função de transição dos estados; • e0 é o estado inicial; e • F os estados finais. Exemplo: O autômato M abaixo reconhece números inteiros e reais (separados por “.”). M = (K, Σ, δ, e0, F), onde: K = (E0 , E1 ,E2 , E3) Σ = (d, .) δ(E0,d) → E1 δ(E1,d) → E1 δ(E1,.) → E2 δ(E2,d) → E3 δ(E3,d) → E3 e0 = E0 F = (E1 , E3) b) Tabela de Transições Uma segunda maneira de representar um autômato finito é por meio de uma tabela de transições de estados, contendo os estados nas linhas e os símbolos do alfabeto nas colunas. O estado inicial é marcado com uma seta e os finais com um círculo. Exemplo: A tabela a seguir representa o autômato do exemplo anterior: Linguagens Formais e Autômatos – 1º Semestre de 2015 d . E0 E1 E1 E1 E2 E2 E3 E3 E3 Diz-se que uma cadeia é aceita por um autômato (pertence à linguagem, gerando uma sentença) se, após o seu processamento o autômato pára em um estado final. Se durante o processamento ocorre uma situação de indefinição, o autômato pára e a sentença não é aceita, como uma transição de e0 seguido de um ponto, no exemplo anterior. c) Diagrama de Estados Um autômato finito pode ser representado por meio de um Diagrama de estados (Grafo), no qual os nodos representam os estados e os arcos, as transições. O estado final é indicado por uma seta e os finais por circunferências concêntricas. Exemplo: Para o exemplo anterior, o diagrama de estados que representa o autômato é mostrado a seguir: Linguagens Formais e Autômatos – 1º Semestre de 2015 4.1.2 – Conversão entre Formato de Reconhecedores Muitas vezes, os diagramas de estados aparecem como primeira forma de representação para os autômatos, por causa de sua apresentação gráfica e facilidade de leitura pelo projetista. Para o computador, entretanto, formas tabulares são indiscutivelmente mais cômodas e eficientes. Assim, a conversão de uma notação para a outra torna-se conveniente para efeito de implementação e de documentação. Para converter diagramas de estados em tabelas de transições, pode-se seguir as seguintes regras: § Cria-se uma linha na tabela de transição para cada estado do diagrama; § Marcam-se os estados finais (de aceitação) e o estado inicial; § Cria-se uma coluna para cada terminal e não terminal utilizados no diagrama; § Cria-se uma coluna adicional para representar quaisquer outros terminais de linguagem que não estejam sendo explicitamente utilizados no diagrama; § Se necessário, cria-se uma coluna adicional para transições em vazio; § Para cada transição do estado i para o estado j, consumindo um átomo α, insere-se, na coluna correspondente a α, da linha correspondente ao estado i, a indicação de transição para o estado j. Note-se que as células da tabela, inicialmente vazias, vão sendo preenchidas com os estados-destino das transições. Note-se ainda que, se o autômato apresentar mais de uma transição partindo do estado i, e consumindo o mesmo átomo, a célula correspondente representará o conjunto dos estados-destino para o caso em questão; e § Proceder analogamente para transições com não-terminais e para transições em vazio, utilizando as colunas correspondentes. A conversão oposta pode ser efetuada de maneira semelhante: § Cria-se, para cada linha da tabela, um estado no diagrama; § Marcam-se os estados iniciais e finais; § Para cada célula da tabela, correspondente ao estado i, e ao consumo de um terminal α, que indique transições para um conjunto de estados-destino{j1,...,jn}, criar , no Linguagens Formais e Autômatos – 1º Semestre de 2015 diagrama de estados. Caminhos orientados do estado i para os estados j1,...,jn, com indicação do consumo do terminal α. Se o conjunto for vazio, nada há a fazer; § Tratar de modo similar as células pertencentes a colunas correspondentes a não- terminais e à transição em vazio; e § Para uma eventual célula não vazia do estado i, pertencente à coluna correspondente a todos os demais terminais não explícitos na tabela, criar para cada um destes terminais (α) caminhos orientados partindo do estado i para cada um dos estados- destino indicados na célula. A conversão da notação de autômatos finitos, de produções para diagramas de estados, bem como a conversão oposta, é trivial, e baseia-se nas regras seguintes: § Levantam-se inicialmente: o conjunto de estados utilizados nas produções ou nos diagramas, o estado inicial e os estados finais do autômato. § As transições com consumo de átomos são mapeadas de uma notação para outra com a seguinte correspondência: (Qi, a) → Qj§ Transições em vazio são mapeadas analogamente. (Qi, ∈) → Qj 4.2 – Reconhecedores Determinísticos e Não-Determinísticos Os reconhecedores podem se dividir em duas categorias: os reconhecedores determinístico e os reconhecedores não-determinísticos. Reconhecedores determinísticos são definidos como aqueles que possuem um único movimento possível para uma dada configuração, enquanto que os reconhecedores não- determinísticos admitem um número finito, maior ou igual a um, de movimentos para cada configuração. Logo, o autômato finito pode ser determinístico (AFD) e não determinístico (AFN). No AFD cada movimento é determinado de uma única forma, enquanto que no AFN existem várias Linguagens Formais e Autômatos – 1º Semestre de 2015 possibilidades de transição para um mesmo símbolo. Em alguns livros cita-se que um AFN pode ter movimentos vazios. Um movimento vazio é uma transição sem leitura de símbolo algum. Isso implica dizer que reconhecedores determinísticos possuem apenas uma seqüência de movimento para cada cadeia aceita. Este é um ponto muito importante quando se está preocupado com desempenho. Felizmente pode-se provar que se dois reconhecedores, um determinístico e outro não-determinístico, definem a mesma linguagem, então é possível mapear qualquer reconhecedor não-determinístico em um determinístico equivalente. Exemplos: AFD AFN 4.3 – O Mapeamento de Autômatos Finitos em Gramáticas Regulares Para completar este estudo sobre autômatos finitos, cumpre mencionar que, às vezes, dado um autômato finito determinístico já montado deseja-se construir uma gramática que gere a mesma linguagem. Esta gramática pode ser construída trivialmente aplicando-se as seguintes regras de mapeamento: § Para cada produção do autômato da forma (q1, x) → q2 construir uma produção gramatical da forma Q1 → xQ2 , onde Q1 e Q2 são não-terminais correspondentes aos estados q1 e q2 respectivamente, e x é um terminal. § Para cada produção (q1, x) → q2 , onde q2 é um estado final do autômato, acrescentar Linguagens Formais e Autômatos – 1º Semestre de 2015 uma produção gramatical da forma Q1 → x à gramática que está sendo construída. Exemplo: Dado o Autômato Finito, representado na tabela, obtém-se a gramática correspondente: t i < n > , A B B E C F D B E C B F D C P: A → tB B → iE B → i C → nF D → , B E → < C E → , B F → > D F → > F → , C A gramática desejada será: G = ( { A, B, C, D, E, F, > , < , , , i, t, n}, {> , < , , , i, t, n}, P, A), onde P é o conjunto das produções da gramática apresentado acima. 3 - Tipos de Gramáticas Segundo a Hierarquia de Chomsky 3.1 - Gramáticas Irrestritas 3.2 - Gramáticas Sensíveis ao Contexto 3.3 - Gramáticas Livres de Contexto 3.4 - Gramáticas Regulares 3.5 - Expressões Regulares 4 – Linguagens Regulares 4.1 - Reconhecedores 4.1.1 – Formato de Reconhecedores 4.1.2 – Conversão entre Formato de Reconhecedores 4.2 – Reconhecedores Determinísticos e Não-Determinísticos 4.3 – O Mapeamento de Autômatos Finitos em Gramáticas Regulares
Compartilhar