Дополнительные примеры контекстно-свободных грамматик

$\left\{ a^{i} b^{j} \mid 2 i=3 j+1\right\}$.

$\left\{ a^{i} b^{j} \mid 2 i \neq 3 j+1\right\}$.

$\left\{ a^{i} b^{j} \mid 2 i \leq 3 j \leq 4 i\right\}$.

$\left\{ a^{i} b^{j} \mid 2 i+3 \leq 3 j \leq 4 i-2\right\}$.

$\left\{ a^{i} b^{j} c^{k} \mid i \geq k\text{ или }j \geq k\right\}$.

$\left\{ a^{i} b^{j} c^{k} \mid i+j=k\right\}$.

$\left\{ a^{i} b^{j} c^{k} \mid j=i+k\right\}$.

$\left\{ a^{i} b^{j} c^{k} \mid j \geq i+k-3\right\}$.

$\left\{ a^{i} b^{j} c^{k} \mid i+j \neq k+3\right\}$.

$\left\{ a^{i} b^{j} c^{k} \mid i+2 j=k\right\}$.

$\left\{ a^{i} b^{j} c^{k} \mid i+2 j \equiv k(\bmod 3)\right\}$.

$\left\{ a^{i} b^{j} c^{k} \mid i+2 j=3 k\right\}$.

$\left\{ a^{i} b^{j} c^{k} \mid i+2 k \geq 3 j\right\}$.

$\left\{ a^{i} b^{j} c^{k} \mid i+2 k \leq 3 j \leq 2 i+3 k\right\}$.

$\left\{ a^{i} b^{j} c^{k} d^{\ell } \mid i+k=j+\ell \right\}$.

$\left\{ a^{i} b^{j} c^{k} d^{\ell } \mid i+k \leq j+\ell +3\right\}$.

$\left\{ a^{i} b^{j} c^{k} d^{\ell } \mid i+2 k=j+3 \ell \right\}$.

$\left\{ a^{i} b^{j} c^{k} d^{\ell } \mid i+2 k \neq j+3 \ell \right\}$.

$\left\{ a^{i} b^{j} c^{k} d^{\ell } \mid i+2 \ell =j+3 k\right\}$.

$\left\{ a^{i} b^{j} c^{k} d^{\ell } \mid i+2 \ell \neq j+3 k\right\}$.

$\left\{ b_{i} \# b_{i+1}^{R} \mid b_{i}\text{ является двоичным представлением целого числа }i, i \geq 0\right\}$.

$\left\{ x^{R} \# y \mid x, y \in \left\{ 0,1\right\}^{*}, x\text{ является подстрокой }y\right\}$.

$\left\{ x^{R} \# y \mid x, y \in \left\{ 0,1\right\}^{*}, x\text{ является подпоследовательностью }y\right\}$. (Строка $x= x_{1} x_{2} \cdots x_{k}$ является подпоследовательностью строки $y=y_{1} y_{2} \cdots y_{n}$, где каждый $x_{i}$ и каждый $y_{j}$ — отдельная буква, если существуют $1 \leq j_{1}<j_{2}<\cdots < j_{k} \leq n$, такие что $y_{j_{\ell }}=x_{\ell }$ для $1 \leq \ell \leq k$.)

$\left\{ a^{m} b y \mid y \in \left(a^{+} b\right)^{n-1}, n>m \geq 1\right\}$.

$\left\{ a^{m} b y \mid y \in \left(a^{+} b\right)^{n-1}, m>n \geq 1\right\}$.

$\left\{ x_{1} \# x_{2} \# \cdots \# x_{n} \mid x_{1}, \ldots , x_{n} \in \left\{ 0,1\right\}^{*},(\exists 1 \leq i<j \leq n) \left[x_{i}=x_{j}^{R}\right]\right\}$.

$\left\{ x_{1} \# x_{2} \# \cdots \# x_{n} \mid x_{1}, \ldots , x_{n} \in \left\{ 0,1\right\}^{*},(\exists 1 \leq i<j \leq n) \left[x_{i} \neq x_{j}\right]\right\}$.

$\left\{ 0,1\right\}^{*}-\left\{ w w w \mid w \in \left\{ 0,1\right\}^{*}\right\}$.

$L=(0+1)^{*}-\left\{ \left(0^{n} 1^{n}\right)^{n} \mid n \geq 1\right\}$.