Visualização do documento
Título
OBTENÇÃO DE GRAMÁTICAS L-SYSTEMS A PARTIR DE CADEIAS DE CARACTERES
Orientador
REGINA CÉLIA COELHO
Autor
EDMAR SANTOS
Palavra chave
L-SYSTEM, PROBLEMA INVERSO, PROBLEMA INVERSO DE LINDENMAYER
Grupo CNPQ
Programa
MS - CIÊNCIA DA COMPUTAÇÃO
Área
CIÊNCIAS EXATAS E DA
Data da defesa
20/02/2008
Nº Downloads
2093
Resumo
O grande problema das abordagens que empregam o uso dos L-systems está justamente na determinação de uma gramática formal que represente apropriadamente o modelo desejado. Na teoria dos L-systems esse problema é conhecido como o Problema Inverso de Lindenmayer, um subcaso dos processos de inferência gramatical. Este trabalho apresenta uma proposta para solucionar o Problema Inverso de Lindenmayer nas classes de gramáticas livres de contexto e determinísticas, além de apresentar estudos sobre a resolução desse problema nas gramáticas não determinísticas. A abordagem desta proposta apresenta uma metodologia que consegue obter uma regra L-system a partir de uma cadeia de caracteres representante do estágio de desenvolvimento de um objeto qualquer. As cadeias utilizadas nos testes são sintetizadas a partir de gramáticas conhecidas, porém são tratadas como de origem desconhecida para assegurar a imparcialidade da metodologia. A idéia aqui apresentada consiste na regressão do crescimento da cadeia analisada por um algoritmo construído com base nas relações de crescimento obtidas a partir de cadeias geradas por gramáticas determinísticas conhecidas. Nos testes realizados, todas as cadeias submetidas no algoritmo puderam ser revertidas em uma regra L-system idêntica à regra original utilizada na síntese da cadeia. Também é interessante notar que a obtenção destas regras ocorreu praticamente em tempo real em todas as gramáticas testadas. Os testes realizados nos estudos das gramáticas não determinísticas utilizadas como exemplos também resultaram em regras exatas.
Abstract
The biggest problem with approaches that employ the use of L-systems is exactly the determining a formal grammar that appropriately represents the desired model. In the L-systems theory this problem is known as the Inverse Problem of Lindenmayer, a subset of processes of grammatical inference. This study proposes a solution for the Inverse Problem of Lindenmayer in context-free and deterministic grammatical classes, in addition to the initial studies on the resolution of this problem in non-deterministic grammars. The approach of this proposal presents a methodology that can obtain an L-system rule from a string representing the development stage of any object. The strings used in the tests were obtained from known grammars, however, they are dealt with as having an unknown origin to assure the impartiality of the methodology. The idea presented here consists in the growth regression of the string analyzed by an algorithm built based on the relations of growth obtained from string generated by known deterministic grammars. In the tests carried out, all the strings submitted to the proposed algorithm could be reverted to an L-system rule identical to the original rule used in the synthesis of the string. It is also interesting to observe that the obtaining of these rules occurred practically in real time with the tested grammars. Tests performed in these studies of the non-deterministic grammars used as examples also resulted in exact rules. KEY-WORDS: L-system, Inverse Problem, Inverse Problem of Lindenmayer, Grammar Inference
