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

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

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

• Доказать, что следующие языки не являются регулярными:
  • $ \{ 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} $$