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

Задача 2.1

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

Вспомним КС-грамматику $G_{4}$ , приведённую в примере 2.4. Для удобства переименуем её переменные в одиночные буквы следующим образом.

\begin{aligned} & E \rightarrow E+T \mid T \\ & T \rightarrow T \times F \mid F \\ & F \rightarrow (E) \mid \mathrm{a} \end{aligned}

Приведите деревья вывода и выводы для каждой строки.

?

(a)

a

(b)

$\mathrm{a}+\mathrm{a}$

(c)

$a+a+a$

(d)

((a))

Задача 2.2

(a)(b)

?

(a)

Используя языки $A=\left\{ \mathrm{a}^{m} \mathrm{~ b}^{n} \mathrm{c}^{n} \mid m, n \geq 0\right\}$ и $B=\left\{ \mathrm{a}^{n} \mathrm{~ b}^{n} \mathrm{c}^{m} \mid m, n \geq 0\right\}$ вместе с примером 2.36, покажите, что класс контекстно-свободных языков не замкнут относительно пересечения.

(b)

Используя пункт (a) и закон де Моргана (теорема 0.20), покажите, что класс контекстно-свободных языков не замкнут относительно дополнения.

Задача 2.3

Ответьте на каждый пункт для следующей контекстно-свободной грамматики $G$ .

\begin{aligned} R & \rightarrow X R X \mid S \\ S & \rightarrow \mathrm{a} T \mathrm{~ b} \mid \mathrm{b} T \mathrm{a} \\ T & \rightarrow X T X \mid X \mid \varepsilon \\ X & \rightarrow \mathrm{a} \mid \mathrm{b} \end{aligned}

?

(a)

Что является переменными $G$ ?

(b)

Что является терминалами $G$ ?

(c)

Какая переменная является начальной для $G$ ?

(d)

Приведите три строки из $L(G)$ .

(e)

Приведите три строки, не принадлежащие $L(G)$ .

(f)

Верно или неверно: $T \Rightarrow \mathrm{aba}$ .

(g)

Верно или неверно: $T \stackrel{*}{\Rightarrow }$ aba.

(h)

Верно или неверно: $T \Rightarrow T$ .

(i)

Верно или неверно: $T \stackrel{*}{\Rightarrow } T$ .

(j)

Верно или неверно: $X X X \stackrel{*}{\Rightarrow }$ aba.

(k)

Верно или неверно: $X \stackrel{*}{\Rightarrow }$ aba.

(l)

Верно или неверно: $T \xrightarrow {*} X X$ .

(m)

Верно или неверно: $T \stackrel{*}{\Rightarrow } X X X$ .

(n)

Верно или неверно: $S \stackrel{*}{\Rightarrow } \varepsilon$ .

(o)

Дайте словесное описание $L(G)$ .

Задача 2.4

Приведите контекстно-свободные грамматики, порождающие следующие языки. Во всех пунктах алфавит $\Sigma$ равен 0,1.

?

(a)

$\left\{ w \mid w\text{ содержит не менее трёх единиц}\right\}$

(b)

$\left\{ w \mid w\text{ начинается и заканчивается одинаковым символом}\right\}$

(c)

$\left\{ w \mid \text{длина } w \text{ нечётна}\right\}$

(d)

$\left\{ w \mid \text{ длина }w\text{ нечётна, и её средний символ равен 0}\right\}$

(e)

$\left\{ w \mid w=w^{\mathcal{R}}, \text{ то есть } w \text{ является палиндромом}\right\}$

(f)

Пустое множество

Задача 2.5

Приведите неформальные описания и диаграммы состояний автоматов с магазинной памятью для языков из упражнения 2.4. Во всех пунктах алфавит $\Sigma$ равен 0,1.

?

(a)

$\left\{ w \mid w\text{ содержит не менее трёх единиц}\right\}$

(b)

$\left\{ w \mid w\text{ начинается и заканчивается одинаковым символом}\right\}$

(c)

$\left\{ w \mid \text{длина } w \text{ нечётна}\right\}$

(d)

$\left\{ w \mid \text{ длина }w\text{ нечётна, и её средний символ равен 0}\right\}$

(e)

$\left\{ w \mid w=w^{\mathcal{R}}, \text{ то есть } w \text{ является палиндромом}\right\}$

(f)

Пустое множество

Задача 2.6

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

Приведите контекстно-свободные грамматики, порождающие следующие языки.

?

(a)

Множество строк над алфавитом $\left\{ \mathbf{a}, \mathbf{b}\right\}$ , в которых букв a больше, чем букв b

(b)

Дополнение языка $\left\{ \mathrm{a}^{n} \mathrm{~ b}^{n} \mid n \geq 0\right\}$

(c)

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

(d)

$\left\{ x_{1} \# x_{2} \# \cdots \# x_{k} \mid k \geq 1, \text{ каждое } x_{i} \in \left\{ \mathrm{a}, \mathrm{b}\right\}^{*}, \text{ и для некоторых } i \text{ и } j, x_{i}=x_{j}^{\mathcal{R}}\right\}$

Задача 2.7

Приведите неформальные словесные описания автоматов с магазинной памятью для языков из упражнения 2.6.

?

Задача 2.8

Покажите, что строка the girl touches the boy with the flower имеет два различных левосторонних вывода в грамматике $G_{2}$ со стр. 103. Опишите словесно два различных смысла этого предложения.

?

Задача 2.9

Приведите контекстно-свободную грамматику, порождающую язык

A=\left\{ \mathrm{a}^{i} \mathrm{~ b}^{j} \mathrm{c}^{k} \mid i=j \text{ или } j=k, \text{ где } i, j, k \geq 0\right\} .

Является ли ваша грамматика неоднозначной? Почему да или почему нет?

?

Задача 2.10

Приведите неформальное описание автомата с магазинной памятью, распознающего язык $A$ из упражнения 2.9.

?

Задача 2.11

Преобразуйте КС-грамматику $G_{4}$ из упражнения 2.1 в эквивалентный МП-автомат, используя процедуру из теоремы 2.20.

?

Задача 2.12

Преобразуйте КС-грамматику $G$ из упражнения 2.3 в эквивалентный МП-автомат, используя процедуру из теоремы 2.20.

?

Задача 2.13

(a)(b)

Пусть $G=(V, \Sigma , R, S)$ — следующая грамматика. $V=\left\{ S, T, U\right\}$ ; $\Sigma =\left\{ 0, \# \right\}$ ; а $R$ — следующее множество правил:

\begin{aligned} S & \rightarrow T T \mid U \\ T & \rightarrow 0 T \mid T 0 \mid \# \\ U & \rightarrow 0 U 00 \mid \# \end{aligned}

?

(a)

Опишите $L(G)$ словесно.

(b)

Докажите, что $L(G)$ не является регулярным.

Задача 2.14

Преобразуйте следующую КС-грамматику в эквивалентную КС-грамматику в нормальной форме Хомского, используя процедуру из теоремы 2.9.

\begin{aligned} & A \rightarrow B A B \mid B \mid \varepsilon \\ & B \rightarrow 00 \mid \varepsilon \end{aligned}

?

Задача 2.15

Приведите контрпример, показывающий, что следующая конструкция не доказывает, что класс контекстно-свободных языков замкнут относительно операции звезды. Пусть $A$ — КС-язык, порождаемый КС-грамматикой $G=(V, \Sigma , R, S)$ . Добавим новое правило $S \rightarrow S S$ и назовём получившуюся грамматику $G^{\prime }$ . Предполагается, что эта грамматика порождает $A^{*}$ .

?

Задача 2.16

Покажите, что класс контекстно-свободных языков замкнут относительно регулярных операций: объединения, конкатенации и звезды.

?

Задача 2.17

Используя результаты упражнения 2.16, приведите ещё одно доказательство того, что каждый регулярный язык является контекстно-свободным, показав, как напрямую преобразовать регулярное выражение в эквивалентную контекстно-свободную грамматику.

?

Упражнения