# Building Greibach Normal Form Grammars Using Genetic Algorithms
## 3 Proposed Algorithm of Grammatical Evolution for Greibach Context-Free Grammars
### The Proposed Genetic Evolution Inference Method  
Step 1 Initialization:  
The three sets of the CNF: N,T,S are defined, whereas P will be estimated in the following steps. N is automatically estimated from the datasets, and T, S are calculated according to \(n_{N}\). In our implementation, all the sets are enumerated to accelerate the computer based processes. According to this approach, the starting symbol S \(\equiv\) 0, and the set T (with \(n_{T}\) symbols) will be the one-to-one map of each unique character or terminal symbol to an integer value. We use the number \(n_{N}\) of non-terminal symbols to generate the set N = \(\{n_{T}+1,...,n_{T}+n_{N}\) }. On Table 1 the enumerated symbols map is shown. In the enumeration map, no integer number is skipped. In order to not interfere with the generality of our algorithm, we choose maximum chromosome length as \(RL_{max}*No_{max}\). The maximum length of each production rule \(RL_{max}\) and the maximum number of production rules \(NoR_{max}\) is used to generate random new chromosomes in the initial population up to the initial population size of the GNF in the first generation. If a random chromosome does not include the starting symbol S in the head of any production rule, this chromosome is discarded and the random generation process is re-activated for this chromosome. Each chromosome is stored in the population pool. An example of the enumeration process with a phenotype to chromosome conversion follows. Let the production rules set P = {S \(\rightarrow\) d A, A \(\rightarrow\) e B C, B \(\rightarrow\) e, C \(\rightarrow\) f}, N = {A,B,C}, T = {d,e,f} and S = {S}. 1. Every terminal and non-terminal is stored to the chromosome. In our example this chromosome is:  
3. The phenotype is converted to an enumerated array as:  
Step 2 Fitness calculation:  
The inverse mapping of each chromosome to the corresponding grammar is estimated. The fitness value is calculated by parsing both positive and negative string databases with each chromosome GNF in the chromosome pool. After parsing the positive and negative examples, the well-known true positive (TP), false negative (FN), false positive (FP) and true negative (TN) rates are estimated. TPs and TNs contribute +1 to the fitness value of each chromosome GNF, while FPs contribute -1 and FNs contribute \(-1+a*D\), where a is the sub-parse parameter defined in the previous paragraph. D is the ratio of the string \begin{table}
\begin{tabular}{c c c} \hline \hline
**Set** & **From** & **To** \\ \hline S & 0 & 0 \\ \hline T & 1 & \(n_{T}\) \\ \hline N & \(n_{T}+1\) & \(n_{T}+n_{N}\). \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Enumerated Symbols maplength successfully parsed. From the above, it is obvious that maximum fitness equals the size of both datasets and minimum fitness equals minus the size of both datasets. An example of the term D calculation follows. Let the production rules set \(\text{P}=\{\text{S}\ \rightarrow\text{d}\ \text{A},\ \text{A}\ \rightarrow\text{e}\ \text{B}\ \text{C},\ \text{B} \rightarrow\text{e},\ \text{C}\ \rightarrow\text{f}\}\), \(\text{N}=\{\text{A,B,C}\}\), \(\text{T}=\{\text{d,e,f}\}\) and \(\text{S}=\{\text{S}\}\) as in the previous example. If the string deefd was in the positive dataset then the term D should be equal to 0.2 as deef can be parsed by the above grammar but in the string deefd only the four out of the five symbols can be reached. Hence, D should be 0.8. If the candidate string was deefde then D should be 0.666 and so forth. Step 3 Convergence check:  
The maximum fitness value of the current population GNFs is compared with the predefined convergence criterion. If the best chromosome fitness surpasses the convergence criterion or the maximum number of generations is reached, we accept the GNF with maximum value as a solution to the inference problem and the algorithm is terminated.