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

Пример 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.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.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)\left[\left|w\right|=\left|x\right|=\left|y\right|=\left|z\right|, w x y z \in L\right]\right\}$ .

(c)

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

(d)

$\left\{ x z \mid \left|w\right|=\left|x\right|=\left|y\right|=\left|z\right|, 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|$ . Покажите, что класс языков, допускаемых линейно ограниченными автоматами с магазинной памятью, в точности совпадает с классом контекстно-свободных языков.

?

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