Банк задач по математике

Пример 3.36

Рассмотрим контекстно-свободную грамматику $G=(\left\{ S\right\} , \left\{ a, b\right\} , R, S)$ с правилами

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

Постройте автомат с магазинной памятью $M$ , такой что $L(M)=L(G)$ .

?

Пример 3.38

Постройте контекстно-свободную грамматику $G$ , такую что $L(G)= L(M)$ , где $M$ — автомат с магазинной памятью из примера 3.29.

?

Пример 3.39

Покажите, что если $A$ — регулярный язык, а $B$ — контекстно-свободный язык, то $A \cap B$ — контекстно-свободный язык.

?

Пример 3.40

Покажите, что $L= \left\{ 0,1\right\}^{*}-\left\{ \left(0^{m} 1^{m}\right)^{n} \mid m, n \geq 1\right\}$ — контекстно-свободный язык.

?

Пример 3.41

Покажите, что если $L_{1}$ — контекстно-свободный язык, а $L_{2}$ — регулярный язык, то частное $L_{1} / L_{2}$ является контекстно-свободным языком.

?

Пример 3.42

Покажите, что если $L$ регулярен, то

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

контекстно-свободен.

?

Задача 3.5.1

(a)(b)(c)(d)

Для каждой из следующих контекстно-свободных грамматик $G$ , следуя процедуре из теоремы 3.35, постройте автомат с магазинной памятью, допускающий язык $L(G)$ :

?

(a)

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

(b)

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

(c)

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

(d)

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

(Теорема 3.35: Для любой контекстно-свободной грамматики $G=(V, \Sigma , R, S)$ существует автомат с магазинной памятью $M$ , такой что $L(M)=L(G)$ . Построение: на входе $x$ сначала помещаем в стек начальный символ $S$ , затем моделируем левый вывод строки $x$ грамматикой $G$ — на каждом шаге, если верхний символ стека — нетерминал $A$ , выбираем правило $A \rightarrow w$ и заменяем $A$ на $w$ в стеке (символы $w$ помещаются по одному с помощью дополнительных временных состояний, поскольку автомат может поместить в стек лишь один символ за один шаг); если верхний символ — терминал $a$ , пытаемся сопоставить его со следующим входным символом, отвергая при несовпадении и иначе удаляя его из стека. Вход допускается ровно тогда, когда стек и вход одновременно исчерпаны.)

Задача 3.5.2

(a)(b)

Для каждого из следующих автоматов с магазинной памятью $M$ , следуя процедуре из теоремы 3.37, постройте контекстно-свободную грамматику, порождающую язык $L(M)$ :

?

(a)

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

(b)

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

(Теорема 3.37: Для любого автомата с магазинной памятью $M=(Q, \Sigma , \Gamma , \delta , q, F)$ существует контекстно-свободная грамматика $G$ , такая что $L(G)=L(M)$ . Построение: сначала преобразуем $M$ в эквивалентный автомат $M^{\prime }$ , который всегда просматривает верхний символ стека (на первом шаге помещаем в стек новый символ дна стека $, а также разрешаем $M^{\prime }$ помещать в стек два символа за один шаг, чтобы по-прежнему можно было заменить один символ). Затем строим $G$ с нетерминалами $\langle q, A, p\rangle$ — по одному на каждую пару состояний $q, p$ и символ стека $A$ , — призванными порождать в точности те строки $x$ , для которых $M^{\prime }$ может перейти из $(q, x, A)$ в $(p, \varepsilon , \varepsilon )$ . Правила грамматики $G$ : (1) для каждой инструкции $(p, B) \in \delta^{\prime }(q, a, A)$ с $\left|B\right|=1$ добавляем $\langle q, A, r\rangle \rightarrow a\langle p, B, r\rangle$ для каждого состояния $r$ ; (2) для каждой инструкции $(p, B A) \in \delta^{\prime }(q, a, A)$ с $\left|B\right|=1$ (символ, помещаемый поверх $A$ ) добавляем $\langle q, A, r\rangle \rightarrow a\langle p, B, r^{\prime }\rangle \langle r^{\prime }, A, r\rangle$ для всех состояний $r, r^{\prime }$ ; и (3) для каждой инструкции $(p, \varepsilon ) \in \delta^{\prime }(q, a, A)$ (снятие $A$ со стека без добавления новых символов) добавляем $\langle q, A, p\rangle \rightarrow a$ . Начальный символ грамматики $G$ — это $\langle s_{1}, \$, f\rangle$ , где $s_{1}$ и $f$ — новые начальное и конечное состояния автомата $M^{\prime }$ .)

Задача 3.5.3

(a)(b)(c)(d)

Постройте автоматы с магазинной памятью, допускающие следующие языки:

?

(a)

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

(b)

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

(c)

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

(d)

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

Задача 3.5.4

(a)(b)(c)(d)

Покажите, что если $L$ — регулярный язык, то каждый из следующих языков контекстно-свободен:

?

(a)

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

(b)

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

(c)

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

(d)

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

Задача 3.5.5

Покажите, что $L_{1} \backslash L_{2}$ — контекстно-свободный язык, если $L_{1}$ контекстно-свободен, а $L_{2}$ регулярен.

?

Задача 3.5.6

(a)(b)(c)

Автомат с двумя магазинными памятями (2-стековый автомат) — это автомат с магазинной памятью, имеющий два стека. На каждом шаге $M$ может, помимо входного символа, читать верхние символы обоих стеков и записывать символы в оба стека. Формально, 2-стековый автомат — это шестёрка $M=(Q, \Sigma , \Gamma , \delta , s, F)$ , где $Q, \Sigma , \Gamma , s, F$ имеют тот же смысл, что и для обычного автомата с магазинной памятью, а $\delta$ — функция переходов

\delta : Q \times (\Sigma \cup \left\{ \varepsilon \right\} ) \times (\Gamma \cup \left\{ \varepsilon \right\} )^{2} \rightarrow 2^{Q \times (\Gamma \cup \left\{ \varepsilon \right\} )^{2}}

Пусть $a \in \Sigma \cup \left\{ \varepsilon \right\}$ , и $u_{1}, u_{2}, v_{1}, v_{2} \in \Gamma \cup \left\{ \varepsilon \right\}$ . Тогда инструкция $\left(p, v_{1}, v_{2}\right) \in \delta \left(q, a, u_{1}, u_{2}\right)$ означает, что автомат $M$ читает входной символ $a$ , верхний символ $u_{1}$ стека 1, верхний символ $u_{2}$ стека 2, а затем переходит в состояние $p$ , заменяет $u_{1}$ на $v_{1}$ и заменяет $u_{2}$ на $v_{2}$ .

?

(a)

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

(b)

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

(c)

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

Задача 3.5.7

Автомат с магазинной памятью $M$ называется линейно ограниченным автоматом, если существует константа $c>0$ , такая что размер стека автомата $M$ в ходе вычисления на любом входе $x$ ограничен величиной $c\left|x\right|$ . Покажите, что класс языков, допускаемых линейно ограниченными автоматами с магазинной памятью, в точности совпадает с классом контекстно-свободных языков.

?

Автоматы с магазинной памятью и контекстно-свободные грамматики