# Tag Info

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