Контекстно-свободные языки

$S \longrightarrow a S a \mid b S b \mid a \mid b$.

$S \longrightarrow a S \mid b S \mid \varepsilon$.

$S \longrightarrow a S \mid S b \mid a$.

$S \longrightarrow S S \mid a \mid b$.

$S \longrightarrow S S \mid a S b \mid \varepsilon$.

$S \longrightarrow a S \mid a S b S \mid \varepsilon$.

Покажите, что следующая грамматика не порождает язык $\left\{ x \in \left\{ 0,1\right\}^{*} \mid x\text{ содержит столько же 0, сколько и 1 }\right\}$ :

Покажите, что следующая грамматика порождает язык $\left\{ x \in \left\{ 0,1\right\}^{*} \mid x\text{ содержит столько же 0, сколько и 1 }\right\}$ :

$10(0+1)^{*} 10$.

$\left((0+11)^{*} 10\right)^{*}$.

Множество двоичных строк, не содержащих подстроку 000.

Множество двоичных строк, у которых суффикс длины десять начинается с 000.

$S \longrightarrow b a S \mid b S \mid \varepsilon$.

$S \longrightarrow S a b \mid S b \mid a b \mid b$.

$S \longrightarrow A \mid B, A \longrightarrow b a A \mid b A \mid \varepsilon , B \longrightarrow B a b \mid B b \mid a b \mid b$.

$S \longrightarrow A B, A \longrightarrow b a A \mid b A \mid \varepsilon , B \longrightarrow B a b \mid B b \mid a b \mid b$.

$S \longrightarrow A A \mid B B, A \longrightarrow b a A \mid b A \mid \varepsilon , B \longrightarrow B a b \mid B b \mid a b \mid b$.

$S \longrightarrow A a b B, A \longrightarrow a A \mid b A \mid \varepsilon , B \longrightarrow B a b \mid B b \mid a b \mid b$.

$S \longrightarrow A B, A \longrightarrow A a \mid A b \mid a \mid b, B \longrightarrow a B \mid a b B \mid \varepsilon$.

$S \longrightarrow A A \mid B, A \longrightarrow a A a \mid b A b \mid a \mid b, B \longrightarrow a B \mid b B \mid \varepsilon$.

$S \longrightarrow A B, A \longrightarrow a A a \mid b A b \mid a \mid b, B \longrightarrow a B \mid b B \mid \varepsilon$.

$\left\{ a^{n} b^{m} \mid m \geq n, m-n\text{ чётно }\right\}$.

$\left\{ x c^{n} \mid x \in \left\{ a, b\right\}^{*}, \#_{a}(x)=n\text{ или }\#_{b}(x)=n\right\}$, где $\#_{a}(x)$ обозначает число вхождений символа $a$ в строку $x$.

$\left\{ x c^{n} \mid x \in \left\{ a, b\right\}^{*}, \#_{a}(x)+\#_{b}(x) \geq n\right\}$.

$\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\}$.

Покажите, что следующая контекстно-свободная грамматика $G$ для арифметических выражений над переменными $a$ и $b$ неоднозначна:

Найдите эквивалентную однозначную грамматику для $L(G)$.

Покажите, что оба решения из примера 3.6 для $L$ неоднозначны:

Найдите однозначную контекстно-свободную грамматику для языка $L$.

Постройте дерево разбора для $a^{3} b^{3} c^{3} a^{6}$.

Покажите, что эта грамматика однозначна.

Покажите, что $G$ неоднозначна.

Найдите однозначную контекстно-свободную грамматику, эквивалентную $G$.

Покажите, что грамматика $G_{3}$ из примера 3.25(b) является сильной $\mathrm{LL}(1)$-грамматикой.

Удовлетворяет ли грамматика из примера 3.24(b) условию леммы 3.26? Удовлетворяет ли она условию сильной $\mathrm{LL}(k)$ хотя бы для одного $k \geq 0$?

Грамматика $G$ неоднозначна тогда и только тогда, когда неоднозначна грамматика $G^{\prime }$, полученная в результате левой факторизации грамматики $G$.

Если после операции левой факторизации грамматика $G$ становится сильной $\mathrm{LL}(k)$-грамматикой, то $G$ обязательно является сильной $\mathrm{LL}(k+1)$-грамматикой. Верно ли обратное?

$S \longrightarrow S_{1} \$, \quad S_{1} \longrightarrow a a S_{1} b \mid b b \mid a b$.

$S \longrightarrow S_{1} \$, \quad S_{1} \longrightarrow a A \mid S_{1} b \mid S_{1} c, \quad A \longrightarrow b A c \mid \varepsilon$.

$S \longrightarrow a S b \mid A, A \longrightarrow a A c \mid \varepsilon$.

$S \longrightarrow A \mid B, A \longrightarrow a A b \mid a b, B \longrightarrow a B c \mid a c$.

$\left\{ a^{n} b^{m} \mid m, n \geq 0, m \neq 3 n\right\} ; x=a^{2} b^{4}$.

$\left\{ a^{n} b^{m} \mid 0 \leq 2 n \leq m \leq 3 n\right\} ; x=a^{2} b^{5}$.

$\left\{ a^{n} b^{m} \mid 0 \leq 2 n \leq 3 m \leq 4 n-2\right\} ; x=a^{3} b^{3}$.

$\left\{ a^{i} b^{j} c^{k} \mid i, j, k \geq 0, i+2 k=j\right\} ; x=a^{3} b^{7} c^{2}$.

$\left\{ a^{i} b^{j} c^{k} \mid i, j, k \geq 0,2 i+3 k \leq 4 j\right\} ; x=a^{4} b^{4} c^{2}$.

$\left\{ a^{i} b^{j} c^{k} d^{l} \mid i, j, k \geq 0, i+k \leq j+l\right\} ; x=a^{2} b^{4} c^{5} d^{3}$.

$\left\{ a^{i} b^{j} c^{k} d^{l} \mid i, j, k \geq 0,2 i+3 k \leq 4 j+l\right\} ; x=a^{3} b^{4} c^{4} d^{5}$.

$\left\{ w \in \left\{ a, b\right\}^{*} \mid 2 \#_{a}(w)+5 \leq 3 \#_{b}(w)\right\} ; x=a b b a b b a$.

$\left\{ w \in \left\{ a, b\right\}^{*} \mid 2 \#_{a}(w) \leq 3 \#_{b}(w) \leq 4 \#_{a}(w)\right\} ; x=a b b a a a b$.

$\left\{ w \in \left\{ a, b, c\right\}^{*} \mid \#_{a}(w) \leq \#_{b}(w)+3 \#_{c}(w)\right\} ; x=a a c a b b b a a$.

$\left\{ w \in \left\{ a, b, c\right\}^{*} \mid 2 \#_{a}(w) \leq \#_{b}(w)+3 \#_{c}(w) \leq 5 \#_{a}(w)\right\} ; x=$ acabcc.

МП-автомату разрешается заносить в стек два стековых символа за один шаг; то есть функция переходов $\delta$ имеет следующий вид:

МП-автомату разрешается заносить в стек любое число стековых символов за один шаг; то есть функция переходов $\delta$ имеет следующий вид:

МП-автомат обязан снимать со стека верхний элемент при каждом шаге и может заносить в стек два стековых символа за один шаг; то есть функция переходов $\delta$ имеет следующий вид:

(Предполагается, что МП-автомат начинает работу со специальным символом $ в стеке, то есть начальная конфигурация есть ($s, x, \$$).)

МП-автомат принимает входную строку, если после завершения чтения входных символов он достигает заключительного состояния (независимо от того, пуст стек или нет); то есть МП-автомат принимает строку $x \in \Sigma^{*}$, если $(s, x, \varepsilon ) \vdash^{*}(q, \varepsilon , \gamma )$ для некоторого $q \in F$ и некоторого $\gamma \in \Gamma^{*}$.

Определите, является ли МП-автомат, заданный в примере, детерминированным.

Если ответ на (a) отрицательный, определите, существует ли эквивалентный детерминированный МП-автомат, принимающий тот же язык. Если да, приведите ваш детерминированный МП-автомат; если нет, покажите почему. [Указание: один из способов устранить (часть) недетерминизма в МП-автомате состоит в использовании модели МП-автомата из упражнения 3(c).]

$S \rightarrow \varepsilon \mid a S b S \mid b S a S$.

$S \longrightarrow \varepsilon \mid S S \mid a S b$.

Грамматика из решения 2 примера 3.6.

Однозначная грамматика из примера 3.24(b).

Автомат из примера 3.30.

Автомат с рисунка 3.14(a) (для языка $\left\{ a^{i} b^{j} \mid 2 i=3 j\right\}$).

$\left\{ 0^{n} 1^{m} \mid m \neq n, m \neq 2 n, m \neq 3 n\right\}$.

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

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

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

$\left\{ x \in L \mid x=x^{R}\right\}$.

$\left\{ w y \mid (\exists x, z)\left[\left|w\right|=\left|x\right|=\left|y\right|=\left|z\right|, w x y z \in L\right]\right\}$.

$\left\{ y x \mid (\exists w, z)\left[\left|w\right|=\left|x\right|=\left|y\right|=\left|z\right|, w x y z \in L\right]\right\}$.

$\left\{ x z \mid \left|w\right|=\left|x\right|=\left|y\right|=\left|z\right|, w x y z \in L\right\}$.

Дайте формальное определение понятий конфигурации и следующей конфигурации 2-стекового автомата.

Постройте 2-стековый автомат, допускающий язык $\left\{ a^{n} b^{n} c^{n} \mid n \geq 0\right\}$.

Постройте 2-стековый автомат, допускающий язык $\left\{ a^{n} b^{m} c^{n} d^{m} \mid n \geq m\right\}$.