Document details

Inference process try to find a generic answer based on a sample of facts. This process aims to achieve a grammar for a particular language based in string samples that belong or not belong to the specific language. In this work we propose an algorithm for context-free grammars inference based in only one sample string that not belongs to the language. The genetic algorithm evolutive technical was applied in order to assist the generation of production rules for grammars. This process must to validate the sample string restrictions. Inference algorithm proposed can be applied in computer languages that have specific pre-defined standards, like schemas for XML documents. Suitability of the proposed algorithm is shown by small experiments where grammars are genetically obtained and generated.

Num processo de inferência, busca-se encontrar uma resposta genérica baseando-se na análise de uma amostra de fatos. A inferência gramatical visa obter uma gramática para uma determinada linguagem baseada em exemplos de cadeias que pertencem ou não à linguagem analisada. Neste trabalho propõe-se um algoritmo para o uso de inferência em gramáticas livres de contexto baseadas em uma cadeia exemplo não pertencente à linguagem. A técnica evolutiva de algoritmos genéticos foi aplicada no processo com o objetivo de auxiliar na criação das regras de produção para as gramáticas, atendendo às restrições impostas pela cadeia exemplo. Uma aplicação do algoritmo de inferência está relacionada a linguagens que possuem padrões específicos pré-definidos, como é o caso de documentos XML no contexto de esquemas. A eficiência do algoritmo proposto é mostrada através de pequenos testes onde são obtidas gramáticas geneticamente geradas.