kmp

Упражнения по языкам и грамматикам

Основные определения

Упражнение 1.1.1. Перечислить слова языка $L_1 \cap L_2$ , где $L_1 = \{ (ab)^n \mid n \geqslant 0 \}$ и $L_2 = \{ a^m b^m \mid m \geqslant 0 \}$ .

Упражнение 1.1.2. Пусть $\Sigma = \{a,b,c\}$ . Равны ли языки $\{ (abc)^n a \mid n \geqslant 2 \}$ и $L_2 = \{ ab (cab)^n ca \mid n \geqslant 1 \}$ ?

Упражнение 1.1.3. Пусть $\Sigma = \{a,b,c\}$ , $L_1 = \{ w \in \Sigma ^* \mid | w | = 4 \}$ и $L_2 = \{ w \in \Sigma ^* \mid | w |_c = 1 \}$ . Сколько слов содержит язык L₁ - L₂?

Упражнение 1.1.4. Пусть даны такие алфавиты $\Sigma_1$ и $\Sigma_2$ , что $\Sigma_1 - \Sigma_2 \neq \varnothing$ . В каком случае $\Sigma_1 ^+ - \Sigma_2 ^* = ( \Sigma_1 - \Sigma_2 )^+$ ?

Операции над языками

Упражнение 1.2.1. При каких положительных целых числах k, l, m, n существуют алфавит $\Sigma$ , язык $L_1 \subseteq \Sigma^*$ и язык $L_2 \subseteq \Sigma^*$ , удовлетворяющие условиям $| \Sigma | = k$ , |L₁| = l, |L₂| = m, $| L_1 \cdot L_2 | = n$

Упражнение 1.2.2. Пусть $\Sigma = \{ a , b \}$ и L = {aa,ab}. Найти L³.

Упражнение 1.2.3. Пусть $\Sigma = \{ a , b , c , d \}$ и

$L = \{ w \in \Sigma ^* \mid | w |_a = 1, \; | w |_c = 1 \} .$

Верно ли, что $abcdcacdcabbacba \in L^*$

Упражнение 1.2.4. Существует ли такой язык L, что выполняется неравенство $L^* \neq \{ x^n \mid x \in L ,\ n \geqslant 0 \}$

Упражнение 1.2.5. Существует ли такой язык L, что выполняется неравенство $(L \reverse)^* \neq (L^*) \reverse$ ?

Упражнение 1.2.6. Существуют ли такие языки L₁ и L₂, что языки $L_1 \cdot ( L_2 \reverse )$ и $L_1 \reverse \cdot L_2$ неравномощны?

Упражнение 1.2.7. Существуют ли такие языки L₁ и L₂, что языки $L_1 \reverse \cdot L_2$ и $L_2 \reverse \cdot L_1$ неравномощны?

Порождающие грамматики

Упражнение 1.4.1. Описать язык, порождаемый грамматикой

$\begin{align*} S \; & {\to} \; F F , \\ F \; & {\to} \; a F b , \\ F \; & {\to} \; ab . \end{align*}$

Упражнение 1.4.2. Описать язык, порождаемый грамматикой

$\begin{align*} C \; & {\to} \; C c , \\ C \; & {\to} \; A , \\ A \; & {\to} \; a A b , \\ A \; & {\to} \; \varepsilon . \end{align*}$

Упражнение 1.4.3. Описать язык, порождаемый грамматикой

$\begin{align*} K \; & {\to} \; \varepsilon , \\ K \; & {\to} \; a , \\ K \; & {\to} \; b , \\ K \; & {\to} \; a K a , \\ K \; & {\to} \; b K b . \end{align*}$

Упражнение 1.4.4. Описать язык, порождаемый грамматикой

$\begin{align*} D \; & {\to} \; D A , \\ D A A \; & {\to} \; A D b , \\ A D A \; & {\to} \; b , \\ A \; & {\to} \; a . \end{align*}$

Упражнение 1.4.5. Описать язык, порождаемый грамматикой

$\begin{align*} F \; & {\to} \; a F H , \\ F \; & {\to} \; a b c , \\ b H \; & {\to} \; b b c , \\ c H \; & {\to} \; H c . \end{align*}$

Упражнение 1.4.6. Описать язык, порождаемый грамматикой

$\begin{align*} S \; & {\to} \; a T S , \\ S \; & {\to} \; U , \\ T a \; & {\to} \; aa T , \\ T U \; & {\to} \; U , \\ U \; & {\to} \; a . \end{align*}$

Упражнение 1.4.7. Эквивалентны ли грамматика

$\begin{align*} S \; & {\to} \; ab , \\ S \; & {\to} \; a K S b , \\ K \; & {\to} \; b S b , \\ K S \; & {\to} \; b , \\ K \; & {\to} \; \varepsilon \end{align*}$

и грамматика

$\begin{align*} S \; & {\to} \; a T b , \\ T \; & {\to} \; \varepsilon , \\ T \; & {\to} \; b , \\ T \; & {\to} \; S , \\ T \; & {\to} \; b S b S ? \end{align*}$

Упражнение 1.4.8. Эквивалентны ли грамматика

$\begin{align*} S \; & {\to} \; aD , \\ D \; & {\to} \; bba , \\ D \; & {\to} \; baDa , \\ D \; & {\to} \; aDaDa \\ \end{align*}$

и грамматика

$\begin{align*} S \; & {\to} \; aaE , \\ S \; & {\to} \; abJ , \\ E \; & {\to} \; bJJ , \\ J \; & {\to} \; aaEa , \\ J \; & {\to} \; abJa , \\ J \; & {\to} \; ba ? \end{align*}$

Классы грамматик

Упражнение 1.5.1. Какому классу принадлежит грамматика

$\begin{align*} S \; & {\to} \; abba , \\ S \; & {\to} \; baa ? \end{align*}$

Упражнение 1.5.2. Какому классу принадлежит грамматика

$\begin{align*} S \; & {\to} \; A D , \\ A \; & {\to} \; a A , \\ A \; & {\to} \; \varepsilon , \\ D \; & {\to} \; b D c , \\ D \; & {\to} \; \varepsilon ? \end{align*}$

Упражнение 1.5.3. Найти праволинейную грамматику, порождающую язык $\{ a^n b^m \mid n \geqslant 1 \text{ или } m \geqslant 1 \}$ .

Упражнение 1.5.4. Найти праволинейную грамматику, эквивалентную грамматике

$\begin{align*} S \; & {\to} \; K bba K, \\ K \; & {\to} \; K a, \\ K \; & {\to} \; K b, \\ K \; & {\to} \; \varepsilon . \end{align*}$

Упражнение 1.5.5. Найти праволинейную грамматику, эквивалентную грамматике

$\begin{align*} S \; & {\to} \; a S b, & K \; & {\to} \; a K, \\ S \; & {\to} \; K, & J \; & {\to} \; J b, \\ S \; & {\to} \; J, & K \; & {\to} \; a, \\ & & J \; & {\to} \; \varepsilon . \end{align*}$