No estudo das linguagens humanas, uma forma de descrever e entender certas características das linguagens é por meio das gramáticas. Por exemplo, a gramática da língua portuguesa descreve e especifica as relações entre nome, complemento e objeto. Na computação, onde é frequente o uso de linguagens de programação, as gramáticas tem papel semelhante, sendo fundamentais no processo de especificação, compilação e entendimento das linguagens.
Vamos Relembrar alguns conceitos.
Alfabeto, Cadeia e Linguagem formal
Uma linguagem formal é uma abstração das características gerais de uma linguagem de programação. A linguagem é um conjunto de cadeias, onde cada cadeia é uma sequência finita de símbolos e um conjunto de símbolos constitui um alfabeto. Possui também regras de formação e sentença.
Gramática
Uma gramatica consiste de uma coleção de regras de substituição, também denominadas produções. Cada regra aparece como uma linha na gramática, compreendendo um símbolo e uma cadeia separados por uma seta. As regras descrevem como as cadeias podem ser formadas.
Linguagem livre de contexto e gramática livre-do-contexto
Uma gramática livre-do-contexto (GLC) é uma gramática formal em que cada regra de produção é da forma: V &rarr? w onde V é um único símbolo não-terminal(variável), e w é uma cadeia de terminais e/ou variáveis (w pode ser a cadeia vazia).
A linguagem livre de contexto (LLC) é uma linguagem gerada por alguma gramática livre de contexto (GLC). Diferentes gramáticas livres de contexto podem gerar a mesma linguagem livre de contexto, ou, inversamente, uma dada linguagem livre de contexto pode ser gerada por diferentes gramáticas livres de contexto.
Ambiguidade
Uma gramática é ambigua quando consegue gerar a mesma cadeia de várias maneiras diferentes. Dizemos que uma linguagem é inerentemente ambígua quando todas as gramáticas que geram essa linguagem são ambíguas, é o caso de algumas linguagens livre de contexto que só podem ser geradas por gramáticas ambíguas.
Formas Normais
A forma normal de Chomsky é uma maneira de simplificar a linguagem livre de contexto. Na forma normal de Chomsky a parte direita de qualquer regra não pode ter mais de dois
símbolos. Estando a gramática na forma normal de Chomsky, para derivar uma cadeia com n símbolos finais são necessárias no máximo 2n-1 produções. Qualquer linguagem livre de contexto, que não possua nem produções-λ?, nem produções vazias, pode ser convertida para uma gramática na forma normal de Chomsky.
Seja uma GLC G = (V, ∑S, R, P), ela é dita estar na Forma Normal de Chomsky (FNC) se todas as regras são da forma:
P →? λ?, se λ? ? L(G)
X →? Y Z, para Y, Z ? V
X →? a, para a ∈? ∑S
Se colocarmos restrições não no número de símbolos da parte direita das produções, mas nas posições relativas admissíveis das variáveis e dos símbolos terminais, teremos a forma normalizada de Greibach. Para toda a gramática livre de contexto G tal que λ? não pertença a linguagem de G, existe uma gramática equivalente G’ na forma normal de Greibach.
Seja uma GLC G = (V, ∑S, R, P), ela é dita estar na Forma Normal de
Greibach (FNG) se todas as regras são da forma:
P →? λ?, se λ? ∈? L(G)
X →? a y, para a ∈? ∑S e y ∈? V**
Existe um algoritmo para passar à forma normal de Greibach a partir da forma normal de Chomski. Este algoritmo pode ser consultado em link(http://www.cs.uky.edu/~lewis/texts/theory/languages/cf-lang.pdf) Temos então uma das principais utilidades da forma normal de Chomsky: é fácil chegar a ela, a partir de qualquer gramática e depois usa-se o algoritmo para passar à de Greibach, o inverso também é possível, ou seja, uma gramática na forma normal de Greibach pode ser transformada na forma normal de Chomsky.
Sabendo disso, vamos analisar a questão 40 do POSCOMP de 2012.
Item I. (Correto) a forma normal de Chomsky limita como as regras podem ser escritas em uma gramática, como é possível gerar uma palavra por duas sequências diferentes de derivação através dessa forma, o item I está correto.
Item II. (Correto) Uma linguagem que não é ambígua, pode ser gerada por uma gramática ambígua. Mesmo que exista uma gramatica não ambígua, também pode existir uma gramatica qualquer que seja ambígua.
Item III. (Correto) Assim como na forma normal de Chomsky, toda gramatica pode ser colocada na forma normal de Greibach, inclusive, o algoritmo da forma normal de Greibach só funciona se a gramatica já estiver na forma normal de Chomsky.
Item IV. (Incorreto) Gramaticas na forma normal de Chomsky não conseguem gerar a palavra vazia, por isso, é necessário remover o ? (passo 3) da linguagem em questão.
Resposta: D.
Grupo PET Computação UFCG, 2013. All rights reserved.
