Grammatical Inference by Wojciech Wieczorek

Author:Wojciech Wieczorek
Language: eng
Format: epub
Publisher: Springer International Publishing, Cham

6.2.2 Our Implementation

Let us assume that a context-free grammar is represented as described on pages 34 and 35. We have got the following form of the GI algorithm:

6.3 Bibliographical Background

Finite language decomposition was investigated for the first time by Mateescu et al. (1998). They discovered the concept of a decomposition set—the subset of the states of the minimal finite deterministic automaton for a regular language (notice that every finite language is regular). In their work, it was also left open whether testing the primality of a finite language is an intractable problem. Wieczorek (2010a) developed this theory and introduced the concept of significant states in DFA. It helped to construct a very clever algorithm for finding decompositions. In the paper we can find two additional algorithms; one of the algorithms is based on a graph which is very similar to the characteristic graph defined in the present chapter. Jastrzab et al. (2016) showed how the main algorithm in Wieczorek (2010a) may be parallelized. Wieczorek (2009) proposed also a few metaheuristic approaches for the decomposability of finite languages.

The problem of obtaining languages applying an operation on smaller languages is also crucial to the theory of formal languages (Ito 2004). Apart from catenation (i.e. the inverse operation to decomposition), the shuffle operation has been intensively studied in formal language theory (Berstel and Boasson 2002). Jedrzejowicz and Szepietowski (2001a) investigated the complexity of languages described by some expressions containing shuffle operator and intersection. The same authors considered the class of shuffle languages which emerges from the class of finite languages through regular operations (union, catenation, Kleene star) and some shuffle operations (Jedrzejowicz and Szepietowski 2001b).

Constructing an initial grammar in the algorithm described in this chapter (the initialG function) is taken from Wieczorek (2010b). A function for eliminating unit productions is an implementation of the algorithm given by Hopcroft et al. (2001).

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.