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

Пример 3.1

Рассмотрим контекстно-свободную грамматику $G_{1}=(\left\{ S\right\} ,\left\{ 0,1\right\} ,\left\{ S \rightarrow \varepsilon \text{, }S \rightarrow 0 S 1\right\} , S)$ . Чему равен язык $L\left(G_{1}\right)$ ?

?

Пример 3.2

Рассмотрим контекстно-свободную грамматику $G_{2}=(\left\{ S, A, B\right\} , \left\{ a, b\right\} , R$ , $S$ ), где $R$ состоит из следующих правил:

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

Чему равен язык $L\left(G_{2}\right)$ ?

?

Пример 3.3

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

L=\left\{ 0^{n} 1^{2 n} \mid n \geq 0\right\}

?

Пример 3.4

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

L=\left\{ x \in \left\{ 0,1\right\} ^{*} \mid x=x^{R}\right\}

?

Пример 3.5

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

L=\left\{ x \in \left\{ a, b\right\} ^{*} \mid \text{ каждый префикс строки } x \text{ содержит не меньше символов } a \text{, чем символов } b\right\} .

?

Пример 3.6

(Повторное рассмотрение) Найдите контекстно-свободную грамматику, порождающую

L=\left\{ x \in \left\{ a, b\right\} ^{*} \mid x \text{ has as many } a \text{ 's as } b \text{ 's }\right\} .

?

Пример 3.8

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

Рисунок 3.1: ДКА для примера 3.8.

?

Пример 3.9

Постройте контекстно-свободную грамматику, порождающую регулярный язык, допускаемый НКА на рисунке 3.2(a).

Рисунок 3.2: Два НКА для примера 3.9.

?

Пример 3.11

Пусть $G$ — регулярная грамматика со следующими правилами:

\begin{array}{ll} S \longrightarrow 01 A \mid 00 B \mid 11, & A \longrightarrow 0 B \mid 1 C \mid 00, \\ B \longrightarrow 0 A \mid 1 B, & C \longrightarrow 01 S. \end{array}

Постройте НКА, допускающий $L(G)$ .

?

Задача 3.1.1

Опишите словами и/или с помощью регулярных выражений язык, порождаемый каждой из следующих контекстно-свободных грамматик:

?

(a)

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

(b)

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

(c)

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

(d)

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

(e)

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

(f)

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

Задача 3.1.2

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

S \longrightarrow a S \mid b T \mid a, \quad T \longrightarrow b T \mid b.

?

Задача 3.1.3

Покажите, что в каждой строке языка $L(G)$ символов $a$ больше, чем символов $b$ , где $G$ — грамматика со следующими правилами:

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

?

Задача 3.1.4

(a)(b)

?

(a)

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

S \longrightarrow 0 S 1 \mid 01 S \mid 1 S 0 \mid 10 S \mid S 01 \mid S 10 \mid \varepsilon .

(b)

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

S \longrightarrow S S \mid 0 S 1 \mid 1 S 0 \mid \varepsilon .

Задача 3.1.5

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

Для каждого из следующих регулярных языков постройте праволинейную грамматику и леволинейную грамматику для него:

?

(a)

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

(b)

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

(c)

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

(d)

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

Задача 3.1.6

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

?

(a)

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

(b)

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

(c)

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

(d)

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

(e)

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

Задача 3.1.7

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

Для каждой из следующих контекстно-свободных грамматик $G$ найдите эквивалентную регулярную грамматику:

?

(a)

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

(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$ .

(c)

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

(d)

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

Задача 3.1.8

Контекстно-свободная грамматика $G=(V, \Sigma , R, S)$ называется линейной, если каждое её правило имеет вид $A \rightarrow x B$ , или $A \rightarrow B x$ , или $A \rightarrow x$ , где $A, B \in V$ и $x \in \Sigma^{*}$ . Покажите, что язык, порождаемый линейной грамматикой, не обязательно регулярен.

?

Задача 3.1.9

(a)(b)(c)

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

?

(a)

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

(b)

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

(c)

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

Контекстно-свободные грамматики