Tag Info

Hot answers tagged context-free-grammar

2

Observe that your language can be written as the product of two context-free languages $$\{a^nb^{n+k}c^k \mid n, k \geqslant 0 \} = \{a^nb^n \mid n \geqslant 0\}\{b^kc^k \mid k \geqslant 0\}$$ which naturally leads to the grammar \begin{align} S &\to S_0S_1 \\ S_0 &\to aS_0b + 1 \\ S_1 &\to bS_1c + 1 \end{align}

1

For $z = a^n b^{n+1} c^{n+2}$, For your case 1: either $v$ or $x$ must start with atleast one $b$ (i.e. $v=bb^*c^*$ or $x=bb^* c^*$). If $i = 0$, the new string will have its $b$s reduced by at least 1. Hence, the new string would be $a^n b^r c^s$ where $r\le (n+1)-1=n$. With that, the new string is not in $L$. For your case 2: If $i = 0$, the new string ...

1

If you want just a context-free grammar with $0<m\leq n$ you could do the following: $$S \to ab \mid aSb \mid aS$$ However, that would allow $n>4m+3$ as well. Therefore we need to make sure that this can't happen: \begin{align} S_1 &\to aS_2b \\ S_2 &\to aTb \mid U \mid \varepsilon\\ T &\to S_2 \mid aS_2 \mid aaS_2 \mid aaaS_2 \\ U &\...

Only top voted, non community-wiki answers of a minimum length are eligible