Exercise 15:

CFG for {an0ban1banm1banmm1I{1,,m}:(n0=iIni)}\{ a^{n_0} b a^{n_1} b \ldots a^{n_{m-1}} b a^{n_m} \mid m\geq 1 \wedge \exists I\subseteq\{1,\ldots,m\}: (n_0 = \sum_{i\in I} n_i) \}
Write a CFG (which will be ambiguous) generating the words of the form an0ban1banm1banma^{n_0}ba^{n_1}b\ldots a^{n_{m-1}} b a^{n_m}, with m1m\geq 1, for which n0n_0 is equal to the sum of a selection of naturals from n1,n2,,nmn_1,n_2,\ldots,n_m, i.e., n0=iInin_0=\sum_{i\in I} n_i where I{1,,m}I\subseteq\{1,\ldots,m\}. Note that, in particular, the selection might be empty, and therefore a word where n0n_0 is 00 is necessarily correct.
Authors: Guillem Godoy / Documentation:
To be able to submit you need to either log in, register, or become a guest.