# Parsing Expression Grammars and Their Induction Algorithm
## 3 Induction Algorithm
### Deterministic Algorithm Used in Initializing a GP Population  
For a set of strings, \(S\), and a letter, \(r\), by a left quotient, denoted by \(r^{-1}S\), we will mean the set \(\{w:rw\in S\}\), i.e., \(a^{-1}\{ax,ax_{1},x_{2}\}=\{x,x_{1}\}\). Let \(X\) and \(Y\) be pairwise disjoint, nonempty sets of words over an alphabet \(\Sigma\). Our aim is to obtain a compact non-circular PEG \(G\) satisfying the following two conditions: (i) \(X\subseteq L(G)\), (ii) \(Y\cap L(G)=\emptyset\). The Algorithm 1 (function \(I(X,Y)\)) does it recursively. ```
1 functionI (\(X\), \(Y\))
2\(A\)\(\leftarrow\) FirstLetters (\(X\)); // set of first letters
3\(B\)\(\leftarrow\) FirstLetters (\(Y\));
4 Declare \(e\) as an empty expression;
5 foreach\(a\in A\)do
6 if\(a\
otin B\)then
7 Append \(e\) with \(\mid a\) or with \(a\) if \(e\) is empty;
8
9 else
10 Append \(e\) with \(\mid a\gg\) I (\(a^{-1}X,a^{-1}Y\));
11
12 if\(e\) is an empty expressionthen
13 return\(\sim\)(\(a\mid b\mid c\mid\ldots\)); // \(\{a\mid b\mid c\mid\ldots\}=B\)
14 if\(X\) has the empty string then
15 Append \(e\) with \(\mid\sim\)(\(a\mid b\mid c\mid\ldots\)) \(\Rightarrow\)\(e\);
16
17 return\(e\);
```  
**Algorithm 1**Inferring a single expression  
The \"Append\" method used in lines 7, 9, and 13 in Algorithm 1 concatenates the existing rule \(e\) with a new expression. The recursive call \(I\) in line 9 cuts sets \(X\) and \(Y\) to words that start with terminal symbol \(a\) and then all words that satisfy this condition are passed with words without the first symbol \(a\) (according to the left quotient). Line 10 is used when set \(A\) is empty. The execution of the algorithm is shown by the following example. The input is \(X=\{abba,\,bbbb,\,abaa,\,abbb,\,bbaa,\,bbab\}\), \(Y=\)_{baaaa, aab,\,babb,\,aaaa,\,baba\}_. Figure 2 shows the successive steps of the algorithm. At the beginning set, \(A\) and \(B\) are determined. The first symbols in the sets of words \(X\), \(Y\) are equal to \(\{a,b\}\). The terminal symbol \(a\) of the set \(A\) belongs to the set \(B\). The string \(a\gg\) is added to the rule \(e\) and the method is recursively invoked with left quotients \(a^{-1}X\) and \(a^{-1}Y\) (left leaf from the root in the Figure 2). In the next step, the \(a\) symbol is not in the set \(B\). From the recursive call, the \(b\) symbol is returned and added to the \(e\) rule. After returning, the same procedure is repeated for the symbol \(b\). The algorithm has the following properties: (i) the \(X\), \(Y\) sets in successive calls are always nonempty, (ii) word lengths can be different, (iii) it always halts after a finite number of steps and returns some PEG, (iv) the resultant PEG is consistent with \(X\) (examples) and \(Y\) (counter-examples), and (v) for random words output PEGs are many times smaller than the input. Properties from (i) to (iii) are quite obvious, (iv) will be proven, and we have checked (v) in a series of experiments, and detailed results are given in the next subsection. Let \(n=|X|+|Y|,m=|\Sigma|\), the length of every word (from \(X\) and \(Y\)) not exceed \(d\), and \(T\) be the running time of the algorithm. Then, for random input words, we can write \(T(n,m,d)=O(n)+mT(n/m,m,d-1)\), which leads to \(O(m^{\min\{d,b\log n\}}n)\). In practice, \(m\) and \(d\) are small constants, so the running time of \(I(X,Y)\) is usually linear with respect to \(n\). **Lemma 1**: _Let \(\Sigma\) be a finite alphabet and \(X\), \(Y\) be two disjoint, finite, nonempty sets of words over \(\Sigma\). If \(x\in X\) and \(e\) is a parsing expression returned by \(I(X,Y)\) then consume(\(e,x\)) \(\
eq\) None._  
We will prove the above by induction on \(k\), where \(k\geq 0\) is the length of \(x\). Basis: We use \(k=0\) as the basis. Because \(k=0\), \(x=e\). Let us consider two cases: (1) \(e\) is the only word in \(X\), and (2) \(|X|\geq 2\).