== Курс "Теория конечных автоматов и формальных грамматик". Задачи. ==

=== Регулярные языки ===


  * Построить детерминированный конечный автомат, эквивалентный приведенному недетерминированному конечному автомату с $ \varepsilon $-переходами:

^       ^  $  \varepsilon $  ^     $ a $     ^    $ b $      ^   $ c $       ^
^ -> $ p $ |  $ \{q,r\} $    | $ \emptyset $ |   $ \{q\} $   |  $ \{r\} $    |
^    $ q $ |  $ \emptyset $  |   $ \{p\} $   |   $ \{r\} $   |  $ \{p,q\} $  |
^  * $ r $ |  $ \emptyset $  | $ \emptyset $ | $ \emptyset $ | $ \emptyset $ |

  * Минимизировать следующий детерминированный конечный автомат:

^      ^    0    ^    1    ^
^ -> A |  **B**  |  **E**  |
^    B |  **C**  |  **F**  |
^  * C |  **D**  |  **H**  |
^    D |  **E**  |  **H**  |
^    E |  **F**  |  **I**  |
^  * F |  **G**  |  **B**  |
^    G |  **H**  |  **B**  |
^    H |  **I**  |  **C**  |
^    I |  **A**  |  **E**  |

  * Доказать, что следующие языки не являются регулярными:
      * $ \{ 0^n 1^n \, | \, n \ge 1 \} $
      * $ \{ 0^n 1^m \, | \, n \ge m \} $


=== Контекстно-свободные языки ===

  * Построить конечный автомат с магазинной памятью, распознающий язык, порождаемый следующей контекстно-свободной грамматикой:
$$ 
\begin{array}{rcl}
    S & \rightarrow & 0 S 1 \; | \; A \\
    A & \rightarrow & 1 A 0 \; | \; S \; | \; \varepsilon \\
\end{array}
$$

  * Построить контекстно-свободную грамматику, порождающую язык, распознаваемый следующим конечным автоматом с магазинной памятью:
$$ P \; = \; (\{p,q\}, \{0,1\}, \{X, Z_0\}, \delta, q, Z_0)$$
$$
\begin{array}{rcl}
    \delta (q, 1, Z_0)          & = &  \{ (q, X Z_0) \} \\
    \delta (q, 1, X)            & = &  \{ (q, X X) \} \\
    \delta (q, 0, X)            & = &  \{ (p, X) \} \\
    \delta (q, \varepsilon, X)  & = &  \{ (q, \varepsilon) \} \\
    \delta (p, 1, X)            & = &  \{ (p, \varepsilon) \} \\
    \delta (p, 0, Z_0)          & = &  \{ (q, Z_0) \} \\
\end{array}
$$

  * Привести следующую контекстно-свободную грамматику к нормальной форме Хомского:
$$ 
\begin{array}{rcl}
    S & \rightarrow & aAa \; | \; bBb \; | \; \varepsilon \\
    A & \rightarrow &   C \; | \; a \\
    B & \rightarrow &   C \; | \; b \\
    C & \rightarrow & CDE \; | \; \varepsilon \\
    D & \rightarrow &   A \; | \; B \; | \; ab \\
\end{array}
$$

  * Доказать, что следующие языки не являются контекстно-свободными:
      * $ \{ a^i b^j c^k \, | \, i < j < k \} $
      * $ \{ a^n b^n c^m \, | \, m \le n \} $

  * Проверить принадлежность строки $ ababa $ языку, порождаемому следующей грамматикой:
$$
\begin{array}{rcl}
    S & \rightarrow & AB \; | \; BC \\
    A & \rightarrow & BA \; | \; a \\
    B & \rightarrow & CC \; | \; b \\
    C & \rightarrow & AB \; | \; a \\
\end{array}
$$