Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)

Альтернативное доказательство

Теорема:

Класс автоматных языков является подмножеством регулярных.

Доказательство:

[math]\triangleright[/math]

Рассмотрим автоматный язык [math]L[/math] и ДКА для него. Для доказательства теоремы достаточно построить регулярное выражение, порождающее язык [math]L[/math]. Пусть наш автомат состоит из [math]n[/math] состояний, и состояние [math]0[/math] — стартовое. Также пусть [math]L_i[/math] — язык, состоящий из слов, которые приводят из состояния [math]i[/math] в терминальное. Заметим, что [math]L_i = \bigcup c L_j[/math] для всех [math] c \in \Sigma [/math] и [math]j[/math] таких, что [math]\delta(i, c)=j[/math]. Действительно, если по слову [math] \alpha [/math] из состояния [math]j[/math] мы можем попасть в терминальное состояние, а между состояниями [math] i [/math] и [math] j [/math] есть переход по символу [math] c [/math], то слово [math] c \alpha [/math] принадлежит языку [math]L_i[/math]. Также, если [math]\varepsilon \in L_i[/math], то есть если состояние является терминальным, то добавим [math]\varepsilon[/math] в объединение для [math]L_i[/math]. Мы получили систему из [math]n[/math] регулярных выражений с [math]n[/math] неизвестными, причем [math] \varepsilon \notin \alpha_{ij}[/math] ([math] \alpha_{ij} [/math] — коэффициент перед [math] j [/math]-й переменной в [math] i [/math]-м уравнении) для всех [math] i [/math] и [math] j [/math], так как в автомате нет [math] \varepsilon [/math]-переходов, а следовательно, система имеет единственное решение. Также заметим, что [math]L_0[/math] содержит все слова, по которым из стартового состояния можно дойти до терминального, но тогда [math]L_0 = L[/math]. В итоге мы построили систему уравнений в регулярных выражениях, решив которую, мы получим регулярное выражение, порождающее язык [math]L[/math].

[math]\triangleleft[/math]

Отметим, что длина построенного таким образом регулярного выражения обычно заметно короче, чем если бы мы строили его по теореме Клини.

Пример

Найдем регулярное выражение для языка двоичных представлений чисел, в которых есть хотя бы один ноль

[math] \begin{cases} L_1 = 1L_1\\ L_2 = 0L_1 + 0L_2 + 1L_2 + \varepsilon \end{cases} [/math]

Найдем [math] L_1 [/math]:

[math]L_1 = 1L_1[/math].

Так как [math] \varepsilon \notin 1 [/math], то [math]L_1 = 1^*[/math].

Выразим [math] L_2 [/math] через [math] L_1 [/math]:

[math]L_2 = 0L_1 + 0L_2 + 1L_2 + \varepsilon[/math]

Откуда [math]L_2 = 01^* (0 + 1)^*[/math].

Теперь найдем регулярное выражение для этого же автомата с помощью теоремы Клини (обычный вариант). Для начала построим таблицу, согласно теореме по шагам:

Выражение	Значения

См. также

• Теорема Клини
• Решение уравнений в регулярных выражениях

Источники информации

• Mathhelpplanet — Теорема Клини
• Deepak D’Souza — Regular Expressions
• Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.: Издательский дом «Вильямс», 2008. — С. 112 — ISBN 978-5-8459-1347-0