Učenie redukčnej analýzy

Abstract

Obsahem předložené práce je výzkum učení redukční analýzy. Redukční analýza je metoda pro zjišt'ování syntaktické správnosti věty pomocí jejího postupného zjednodušování až do podoby, o jejíž správnosti je snadné rozhodnout. Modelem redukční analýzy jsou takzvaně restartovací automaty. Tato práce se zabývá učením restartovacích automatů ze vstupu tvořeného množinou příkladů a protipříkladů slov a příkladů a protipříkladů redukcí. V rámci této práce byl navržen a implementován systém pro učení redukční analýzy pro formální jazyky pomocí genetických algoritmů s využitím předpokladu, že možné redukce se dají popsat pomocí vhodné omezených regulárních jazyků, takzvaných striktně lokálně testovatelných jazyků. Součástí práce jsou i experimenty s navrženým systémem na vybraných jazycích.

In the present work is discussed the problem of learning of analysis by reduction. Analysis by reduction is a method for checking syntactic correctness of sentences. This method consists in stepwise simpli cation of the extended sentence until it can be easily accepted or an error is found. It can be modelled by so called restarting automata. In this work is studied methods for learning restarting automata from a given set of positive and negative examples of words and positive and negative examples of reductions. In frame of this work is suggested and implemented a system for learning of analysis by reduction for formal languages using genetic algorithms. The assumption is that the reductions can be described by a subclass of regular languages called strictly locally testable languages. This work includes experiments with suggested system and some selected formal languages too.