A Implementação da forma normal de Chomsky
Por: janadro • 4/4/2018 • Trabalho acadêmico • 1.032 Palavras (5 Páginas) • 434 Visualizações
UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ
DEPARTAMENTO ACADEMICO DE INFORMÁTICA
CIÊNCIA DA COMPUTAÇÃO
JANAINE DAIANE RODRIGUES
LEANDRO CHESINI
IMPLEMENTAÇÃO DA FORMA NORMAL DE CHOMSKY
RELATÓRIO
PONTA GROSSA
2017
SUMÁRIO
1 INTRODUÇÃO 2
2 FORMA NORMAL DE CHOMSKY 3
2.1 GRAMATICA LIVRE DE CONTEXTO 3
2.2 SIMPLIFICAÇÃO 4
2.2.1 Eliminação de produções vazias 4
2.2.2 Exclusão das produções que excluem variáveis 5
2.3 FORMA NORMAL DE CHOMSKY 6
2.3.1 Transformação das produções de tamanho maior ou igual a dois 6
2.3.2 Transformações das produções de tamanho maior ou igual a três 7
3 CONCLUSÃO 8
4 REFERÊNCIAS 9
- INTRODUÇÃO
Gramáticas Livres de Contexto é um tema recorrente na área de Teoria Computacional, muito usada e estudada quando se trata de formalismo. Existem diversas maneiras de trabalha com as GLC, nesse documento vamos ilustrar um algoritmo elabora em linguagem c, para a verificação de algumas gramáticas para saber se não gramáticas livres de contexto, a simplificação e a normalização pela Forma Normal de Chomsky.
- FORMA NORMAL DE CHOMSKY
Para uma gramática livre de contexto, se encontrar na Forma Normal de Chomsky necessita-se que ocorram três etapas de normalização, para que a FNC seja obtida: Simplificação da gramática, Transformação das produções de tamanho maior ou igual a dois, Transformação das produções de tamanho maior ou igual a três.
- GRAMATICA LIVRE DE CONTEXTO
Antes de se aplicar a simplificação da gramatica, precisa-se verificar se a gramática a ser analisada é uma gramática livre de contexto, ou seja, se não existe mais de dois símbolos a esquerda dela, para a verificação de tal condição elaborou-se a seguinte função:
[pic 1]
Onde há uma verificação na terceira posição do vetor de caracteres que representa a gramática, se tal for diferente do símbolo “>” significa que a gramática testada não é uma livre de contexto, para caso de teste temos:
Para gramáticas válidas
[pic 2]
Para gramáticas não válidas:
[pic 3]
- SIMPLIFICAÇÃO
Para aplicar a Forma Normal de Chomsky, deve-se seguir algumas etapas, a etapa da simplificação é a primeira, e tal etapa também necessita que passos sejam seguidos para sua realização.
- Eliminação de produções vazias
Na primeira etapa de simplificação de uma gramática precisa-se eliminar a produções de palavras vazias essas produções vazias podem ser geradas diretamente A→ε ou indiretamente A→Bb|bε, para a representação do símbolo ε, utilizou-se a letra v, na função desenvolvida no algoritmo para a normalização.
[pic 4]
Caso o usuário utilize a letra v maiúscula o algoritmo também entendera que tal quer representar palavra vazia. Para verificar o funcionamento da função realizou-se os seguintes testes:
Palavra que gera produção vazia:
[pic 5]
Palavra que não gera produção vazia:
[pic 6]
- Exclusão das produções que excluem variáveis
A segunda etapa da simplificação de uma gramática é a verificação se a gramática tem um comportamento do tipo A→B, ou seja, uma gramática “chega” na outra de maneira direta ou indireta, de forma a testar essa etapa elaborou-se a seguinte função:
...