# Building Greibach Normal Form Grammars Using Genetic Algorithms
## 1 Introduction  
The theory of formal languages and grammars focuses on the description and the properties of sequences of symbols. Practical applications of this theory include the design of computer programming languages, compilers, computer processing of artificial and natural language texts, speech recognition and speech synthesis, computational biology problems dealing with biological sequences, processing, information extraction, annotation of web pages etc. A Context-Free Grammar (CFG) is a 4-tuple G = (N,T,P,S), whereas N is a set of non-terminal symbols or variables, T is a set of terminal symbols, P is the set of production rules and S is the starting symbol. The rules in P have the form A \(\rightarrow\) a, a \(\in(\text{N}\cup\text{T})^{\star}\) and A \(\in(\text{N}\cup\text{S})\), whereas * is the Kleene star. Footnote *: [[https://www.mdpi.com/journal/signals](https://www.mdpi.com/journal/signals)]([https://www.mdpi.com/journal/signals](https://www.mdpi.com/journal/signals))  
A string of terminal symbols can be generated by a CFG when starting from the symbol S and replacing continuously one variable of the string with the right part of a production rule included in P. The process is terminated when all variables in the string are eliminated. The finite or infinite set of all possible sentences generated by the CFG defines the corresponding language L(CFG) of the grammar. Typically, the description length of the CFG is significantly lower than the L(CFG), therefore CFGs are preferred in computer applications to encode and process artificial and natural languages due their compact description. The inverse problem is known as the grammatical inference problem and is defined by a process to derive a CFG, given a finite sample of the language L(CFG) and a set of sentences not belonging to the L(CFG). Grammatical Evolution (GE) [1] is a hybrid computation technique which is used to solve the grammatical inference problem, combining genetic optimization methods [2] and CFG, mainly in the Backus-Naur Form (BNF). Grammatical Evolution has been used in a variety of optimization problems with many variants and hybrid implementations with other well-known algorithms. Such variants with the use of heuristics and stochastic methods [3; 4; 5], with some rather interesting results, are common in this field. Moreover, GE has been used successfully with Neural Networks (NN) [6] or other Machine Learning (ML) methods such as SVMs [7]. Due to the strictness of the BNF representation of CFG, it is common for Grammatical Evolution(GE) algorithms to generate new chromosomes--through the operations of crossover and mutation--that are either not in the BNF form or even worse are not CFGs. In that case, these chromosomes should be dismissed and some other heuristic techniques must be used. It is clear that grammatical inference methods are a necessity in many applications where CFGs can be extracted from artificial or real string datasets. There have been many methods proposed for the inference problem both analytic [8, 9], evolutionary [10, 11] or using ant colony optimization tools [12]. In many cases, the complexity of the proposed method is polynomial and/or complex structures such as meta-grammars are introduced [13], which often increase the complexity of the proposed method. Recently, the estimation of CFGs from positive and negative samples is derived as a Boolean satisfiability problem (SAT) [14]. The set of training strings is encoded and limits on the sizes of rule sets in Chomsky Normal Form (CNF) are used by a SAT solver to define the CFG. The experimental results suggest that the complexity of inferring CFG is related to its theoretical limitations. In [15, 16], the tabular representation algorithm (TBL) and as an improved version is applied for CNF inference, using a dynamic programming method to store the exponential number of all possible grammatical structures in table similar to CYK of polynomial size. A genetic algorithm is used to solve the NP-hard partitioning problem of the non-terminals set.