Неограниченные грамматики

Найдите грамматику $G$ такую, что $L(G)=\left\{ a^{n} b^{n} c^{n} \mid n \geq 0\right\}$.

Найдите грамматику $G$ такую, что $L(G)=\left\{ a^{2^{n}} \mid n \geq 0\right\}$.

Найдите грамматику $G$ такую, что $L(G)=\left\{ w w \mid w \in \left\{ a, b\right\}^{*}\right\}$.

Найдите грамматику $G$ такую, что $L(G)=\left\{ a^{n} b^{m} c^{n m} \mid n, m \geq 0\right\}$.

Рассмотрим грамматику $G_{1}$ с нетерминалами $V=\left\{ S, A, B, C\right\}$, терминалами $\Sigma = \left\{ a, b, c\right\}$ и правилами

Рассмотрим грамматику $G_{2}$ с нетерминалами $V=\left\{ S, A, L, L_{h}, R,[],\right\}$, терминалом $\Sigma =\left\{ a\right\}$ и правилами

Постройте грамматики для каждого из следующих языков. Также приведите (i) вывод заданной строки $x$ и (ii) доказательство того, почему ваша грамматика не порождает ни одной строки, не принадлежащей языку.

Рассмотрим новую вычислительную модель, называемую маркированными алгоритмами Маркова (Labeled Markov Algorithm, LMA). LMA $M$ определяется как тройка $(\Sigma , \Gamma , P)$, где $\Sigma$ — входной алфавит, $\Gamma$ — рабочий алфавит с $\Sigma \subseteq \Gamma$, а $P$ — программа, состоящая из конечной последовательности $r_{1}, r_{2}, \ldots , r_{n}$ инструкций. Каждая инструкция $r_{i}$ в $P$ имеет вид

где $\alpha , \beta \in \Gamma^{*}$, а $j$ — положительное целое число ($\alpha \rightarrow \beta$ называется правилом вывода, а $L_{j}$ называется меткой следующей инструкции). Инструкция ($L_{i}$ : $\alpha \rightarrow \beta$; goto $L_{j}$;) может быть применена к строке $w \in \Gamma^{*}$, если $\alpha$ является подстрокой $w$. Применение этой инструкции к $w$ порождает новую строку $x$ путём замены самого левого вхождения $\alpha$ в $w$ на $\beta$.

На входе $w \in \Sigma^{*}$ LMA $M$ работает следующим образом: в любой момент вычисления она хранит текущую сентенциальную форму $w$ и текущую метку инструкции $L_{i}$. Изначально $w$ — это входная строка, а текущая метка инструкции — $L_{1}$. На каждом шаге она находит наименьшее целое число $k \geq i$, где $L_{i}$ — текущая метка инструкции, такое что инструкция $r_{k}$ применима к $w$. Затем она применяет $r_{k}$ к $w$, чтобы получить новую сентенциальную форму $x$. Она заменяет $w$ на $x$ и заменяет текущую метку инструкции $L$ на метку следующей инструкции $r_{k}$. Если ни одна инструкция $r_{k}$ с $k \geq i$ не применима к текущей сентенциальной форме $w$, то машина останавливается с результатом $w$. (В частности, если текущая метка инструкции равна $L_{i}$, где $i$ больше числа $n$ инструкций в $P$, то машина останавливается.)

Для произвольной LMA $M$ определим $L(M)=\left\{ x \in \Sigma^{*} \mid M\text{ останавливается на }x\right\}$. Мы говорим, что $M$ вычисляет частичную функцию $f: \Sigma^{*} \rightarrow \Gamma^{*}$, если $M$ останавливается на каждом входе $x \in \operatorname {Domain}(f)$ с финальной сентенциальной формой $w=f(x)$, и $M$ не останавливается ни на каком $x \notin \operatorname {Domain}(f)$.