# Parsing Expression Grammars and Their Induction Algorithm
## 3 Induction Algorithm
### Deterministic Algorithm Used in Initializing a GP Population
In the first case, lines 5-9 of the algorithm are skipped and (in line 11) \(e=\sim\)(\(a\mid b\mid c\mid\ldots\)) is returned, where \(a\), \(b\), \(c\), \(\ldots\) are the first letters of \(Y\) (since \(e\) is in \(X\), \(Y\) has to contain at least one nonempty word). consume(\(a\mid b\mid c\mid\ldots\), \(e\)) = None implies consume(\(e,\epsilon)=0\). In the second case, the loop in lines 5-9 and line 13 are executed, so the returned expression \(e\) (in line 14) has the following form: \(\alpha_{1}\mid\alpha_{2}\mid\cdots\mid\alpha_{j}\mid\sim\)(\(a\mid b\mid c\mid\ldots\)) \(\gg e\), where \(\alpha_{i}\) is a single letter, say \(r_{i}\), or \(r_{i}\gg\beta_{i}\) with \(\beta_{i}\) being some parsing expression. For such an \(e\), consume(\(e,\epsilon)=0\) holds too. Induction: Suppose that \(|x|=k+1\) and that the statement of the lemma holds for all words of length \(j\), where \(0\leq j\leq k\). Let \(x=uw\), where \(u\in\Sigma\). Obviously \(|w|=k\). Again let us consider two cases: (1) \(u\
otin B\), and (2) \(u\in B\). In the first case, \(e\), which is returned in line 14, has the form \(u\mid\alpha\) or \(\alpha\mid u\mid\beta\) or \(\alpha\mid u\), where \(\alpha\) and \(\beta\) are some expressions. In either case consume(\(e,uw\)) \(\geq 0\) (at least \(u\) will not fail for \(x=uw\)). In the second case, \(e\), which is returned in line 14, is a sequence of addends, one of which is \(u\gg\alpha\), where \(\alpha=I(u^{-1}X,u^{-1}Y)\). Suffix \(w\) is an element of the set \(u^{-1}X\) so we invoke the inductive hypothesis to claim that consume(\(\alpha,w\)) \(\
eq\) None. Then consume(\(e,uw\)) \(\
eq\) None, because of the properties of the sequence and the prioritized choice operators (at least \(u\gg\alpha\) will not fail for \(x\)). Lemma 2: _Let \(\Sigma\) be a finite alphabet and \(X\), \(Y\) be two disjoint, finite, nonempty sets of words over \(\Sigma\). If \(y\in Y\) and \(e\) is a parsing expression returned by \(I(X,Y)\) then consume(\(e,y  
Basis: We use \(k=0\) as the basis, i.e., \(y=e\). Because \(e\
otin X\), the returned (in line 13) expression \(e\) has the following form: \(\alpha_{1}\mid\alpha_{2}\mid\dots\mid\alpha_{j}\), where \(\alpha_{i}\) is a single letter, say \(r_{i}\), or \(r_{i}\gg\beta_{i}\) with \(\beta_{i}\) being some parsing expression. For such an \(e\), \(\text{consume}(e,e)=\text{None}\). Induction: Suppose that \(|y|=k+1\) and that the statement of the lemma holds for all words of length \(j\), where \(0\leq j\leq k\). Let \(y=uw\), where \(u\in\Sigma\). Naturally \(|w|=k\). There are two main cases to consider: (1) \(A\) is empty (that happens only when \(X=\{e\}\)), and (2) \(A\) is not empty. In the first case, \(e=\sim\)(\(a\mid b\mid c\mid\dots\mid u\mid\dots\)) is returned, where \(a\), \(b\), \(c\), \(\dots\), \(u\), \(\dots\) are the first letters of \(Y\) (the position of \(u\) in the sequence is not important). \(\text{consume}(a\mid b\mid c\mid\dots\mid u\mid\dots,uw)=1\) implies \(\text{consume}(e,y)=\text{None}\). In the second case (i.e., \(A\) is not empty), let us consider four sub-cases: (2.1) \(u\in A\) and \(e\in X\), (2.2) \(u\in A\) and \(e\
otin X\), (2.3) \(u\
otin A\) and \(e\in X\), and (2.4) \(u\
otin A\) and \(e\
otin X\). As for (2.1), the returned expression \(e\) is of the following form: \(\alpha_{1}\mid\alpha_{2}\mid\dots\mid\alpha_{j}\mid\sim\)(\(a\mid b\mid c\mid\dots\mid u\mid\dots)\gg\epsilon\), where \(\alpha_{i}\) is a single letter, say \(r_{i}\), or \(r_{i}\gg\beta_{i}\) with \(\beta_{i}\) being some parsing expression. Exactly one of \(\alpha_{i}\) has the form \(u\gg\beta_{i}\) (exactly one \(r_{i}=u\)), where \(\beta_{i}=I(u^{-1}X,u^{-1}Y)\). Suffix \(w\) is an element of the set \(u^{-1}Y\) so by the induction hypothesis \(\text{consume}(\beta_{i},w)=\text{None}\). Then \(\text{consume}(e,uw)=\text{None}\). Notice that the last addend--i.e., the one with \(e\)--will also fail due to \(\text{consume}(\sim\)(\(a\mid b\mid c\mid\dots\mid u\mid\dots\)), \(uw)=\text{None}\). Sub-case (2.2) is provable similarly to (2.1).