3
Write $L$ in the following way:
$$
L = \{ a^sbc^s : s \in \mathbb{N}^+ \} \cup \{ a^sb^2c^{2s} : s \in \mathbb{N}^+ \} \cup \{ a^sb^3c^{3s} : s \in \mathbb{N}^+ \}.
$$
1
Hint 1: $L = L_1 \cup L_2$ for some $L_1$ and $L_2$ which are obviously context-free.
Hint 2:
1
Your context-free grammar is just fine. It is not actually necessary for the grammar to have a production with $S$ in its right-hand side. In fact, a context-free grammar need not have any recursive productions or mutually-recursive productions, though the generated language in that case may be quite limited. It is also not necessary to use any particular ...
1
Use nondeterminism to guess an index $i$ for which $w_i \neq w_{i+1}$. The machine reads its input until it nondeterministically chooses a $w_i$ and places it on the stack. Afterwards, it compares $w_{i+1}$ to the content on the stack symbol by symbol. If the comparison fails, the machine accepts.
Only top voted, non community-wiki answers of a minimum length are eligible
