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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 5: Строка 5:
 
|proof=
 
|proof=
  
[[file:Автомат1.png|200px|right]]
 
 
Рассмотрим автоматный язык <tex>L</tex> и ДКА для него. Для доказательства теоремы достаточно построить регулярное выражение, порождающее язык <tex>L</tex>.
 
Рассмотрим автоматный язык <tex>L</tex> и ДКА для него. Для доказательства теоремы достаточно построить регулярное выражение, порождающее язык <tex>L</tex>.
 +
Пусть наш автомат состоит из <tex>n</tex> состояний, и состояние <tex>0</tex> {{---}} стартовое. Также пусть <tex>L_i</tex> {{---}} язык, состоящий из слов, которые приводят из состояния <tex>i</tex> в терминальное.
  
Пусть наш автомат состоит из <tex>n</tex> состояний, и состояние <tex>0</tex> — стартовое. Также пусть <tex>L_i</tex> — язык, состоящий из слов, которые приводят из состояния <tex>i</tex> в терминальное.
+
Заметим, что <tex>L_i = \sum c L_j</tex> для всех <tex> c \in \Sigma </tex> и <tex>j</tex> таких, что <tex>\delta(i, c)=j</tex>. Действительно, если по слову <tex> \alpha </tex> из состояния <tex>j</tex> мы можем попасть в терминальное состояние, а между состояниями <tex>i</tex> и <tex>j</tex> есть переход по символу <tex>с</tex>, то слово <tex>с \alpha</tex> принаджелит языку <tex>L_i</tex>. Также, если <tex>\epsilon \in \L_0</tex>, то есть если стартовое состояние является и терминальным тоже, то добавим в сумму для <tex>L_0</tex> и <tex>\epsilon</tex>.
 
 
Заметим, что <tex>L_i = \bigcup c L_j</tex> для всех <tex> c \in \Sigma </tex> и <tex>j</tex> таких, что <tex>\delta(i, c)=j</tex>. Действительно, если по слову <tex> \alpha </tex> из состояния <tex>j</tex> мы можем попасть в терминальное состояние, а между состояниями <tex> i </tex> и <tex> j </tex> есть переход по символу <tex> c </tex>, то слово <tex> c \alpha </tex> принадлежит языку <tex>L_i</tex>. Также, если <tex>\varepsilon \in L_i</tex>, то есть если состояние является терминальным, то добавим <tex>\varepsilon</tex> в объединение для <tex>L_i</tex>.
 
 
 
Мы получили [[Решение уравнений в регулярных выражениях#Решение системы уравнений в регулярных выражениях | систему]] из <tex>n</tex> регулярных выражений с <tex>n</tex> неизвестными, причем <tex> \varepsilon \notin \alpha_{ij}</tex> (<tex> \alpha_{ij} </tex> {{---}} коэффициент перед <tex> j </tex>-й переменной в <tex> i </tex>-м [[Решение уравнений в регулярных выражениях#Решение системы уравнений в регулярных выражениях | уравнении]]) для всех <tex> i </tex> и <tex> j </tex>, так как в автомате нет <tex> \varepsilon </tex>-переходов, а следовательно, система имеет единственное решение. Также заметим, что <tex>L_0</tex> содержит все слова, по которым из стартового состояния можно дойти до терминального, но тогда <tex>L_0 = L</tex>.
 
 
 
В итоге мы построили систему уравнений в регулярных выражениях, решив которую, мы получим регулярное выражение, порождающее язык <tex>L</tex>.
 
}}
 
 
 
Отметим, что длина построенного таким образом регулярного выражения обычно заметно короче, чем если бы мы строили его по [[Теорема Клини (совпадение классов автоматных и регулярных языков) | теореме Клини]]. Кроме того, построение регулярного выражения таким образом обычно гораздо проще (выполняется за меньшее количество шагов).
 
  
 +
Заметим, что <tex>L_0 = L</tex>.
 +
}}
 
== Пример ==
 
== Пример ==
=== Система уравнений ===
 
[[Файл:at_least_one_zero.png|right]]
 
Найдем регулярное выражение для языка двоичных представлений чисел, в которых есть хотя бы один ноль. Для этого составим уравнение, добавляя соответствующие переменные в правую часть при наличии перехода по символу, а так же <tex>\varepsilon</tex> для терминального состояния, как это указано в доказательстве.
 
 
<tex>
 
\begin{cases}
 
L_1 = 1L_1\\
 
L_2 = 0L_1 + 0L_2 + 1L_2 + \varepsilon 
 
\end{cases}
 
</tex>
 
 
Найдем <tex> L_1 </tex>:
 
 
<tex>L_1 = 1L_1</tex>.
 
 
Так как <tex> \varepsilon \notin 1 </tex>, то <tex>L_1 = 1^*</tex>.
 
 
Выразим <tex> L_2 </tex> через <tex> L_1 </tex>:
 
 
<tex>L_2 = 0L_1 + 0L_2 + 1L_2 + \varepsilon</tex>
 
 
Откуда <tex>L_2 = 01^* (0 + 1)^*</tex>.
 
 
=== Обычный вариант ===
 
 
Теперь найдем регулярное выражение для этого же автомата с помощью теоремы Клини (обычный вариант).
 
Для начала построим таблицу, согласно [[Теорема_Клини_(совпадение_классов_автоматных_и_регулярных_языков) | теореме]] по шагам:
 
 
{| border="1" class="wikitable" style="width: 250px; height: 250px; float: left;"
 
!style="background:#41aef0"|Выражение
 
!style="background:#41aef0"|Значения
 
|-
 
|<tex>R_{11}^{(0)}</tex>
 
|<tex>\varepsilon + 1</tex>
 
|-
 
|<tex>R_{12}^{(0)}</tex>
 
|<tex>0</tex>
 
|-
 
|<tex>R_{21}^{(0)}</tex>
 
|<tex>\varnothing</tex>
 
|-
 
|<tex>R_{22}^{(0)}</tex>
 
|<tex>(\varepsilon + 0 + 1)</tex>
 
|}
 
<div style="clear:both;"></div>
 
 
Например, в выражении <tex>R_{11}^{(0)}</tex> присутствует член <tex>\varepsilon</tex>, потому что и начальным, и конечным является состояние <tex>1</tex>. Это выражение включает также <tex>1</tex>, поскольку существует путь
 
из состояния <tex>1</tex> в состояние <tex>1</tex> по входу <tex>1</tex>. Выражение <tex>R_{12}^{(0)}</tex> равно <tex>0</tex>, потому что есть дуга с
 
меткой <tex>0</tex>, ведущая из состояния <tex>1</tex> в состояние <tex>2</tex>. Здесь нет члена <tex>\varepsilon</tex>, поскольку начальное
 
и конечное состояния различаются. И, наконец, <tex>R_{21}^{(0)} = \varnothing</tex>, так как нет путей, ведущих из
 
состояния <tex>2</tex> в состояние <tex>1</tex>.
 
Теперь применим индукцию для построения более сложных выражений.
 
 
Правило для вычисления выражения <tex>R_{ij}^{(1)}</tex> представляет собой пример общего правила из части теоремы Клини:
 
 
<tex>R_{ij}^{(1)} = R_{ij}^{(0)} + R_{i1}^{(0)} (R_{11}^{(0)})^* R_{1j}^{(0)}</tex>
 
 
{| border="1" class="wikitable" style="width: 300px; height: 250px; float: left;"
 
!style="background:#41aef0"|Выражение
 
!style="background:#41aef0"|Прямая подстановка
 
!style="background:#41aef0"|Упрощенное выражение
 
|-
 
|<tex>R_{11}^{(1)}</tex>
 
|<tex>\varepsilon + 1 + (\varepsilon + 1)(\varepsilon + 1)^*(\varepsilon + 1)</tex>
 
|<tex>1^*</tex>
 
|-
 
|<tex>R_{12}^{(1)}</tex>
 
|<tex>0 + (\varepsilon + 1)(\varepsilon + 1)^*0</tex>
 
|<tex>1^*0</tex>
 
|-
 
|<tex>R_{21}^{(1)}</tex>
 
|<tex>\varnothing + \varnothing(\varepsilon + 1)^*(\varepsilon + 1)</tex>
 
|<tex>\varnothing</tex>
 
|-
 
|<tex>R_{22}^{(1)}</tex>
 
|<tex>\varepsilon + 0 + 1 + \varnothing(\varepsilon + 1)^*0</tex>
 
|<tex>(\varepsilon + 0 + 1)</tex>
 
|}
 
<div style="clear:both;"></div>
 
 
И, наконец, последний шаг индукции
 
 
{| border="1" class="wikitable" style="width: 300px; height: 250px; float: left;"
 
!style="background:#41aef0"|Выражение
 
!style="background:#41aef0"|Упрощенное выражение (после подстановки)
 
|-
 
|<tex>R_{11}^{(1)}</tex>
 
|<tex>1^*</tex>
 
|-
 
|<tex>R_{12}^{(1)}</tex>
 
|<tex>1^*0(0 + 1)^*</tex>
 
|-
 
|<tex>R_{21}^{(1)}</tex>
 
|<tex>\varnothing</tex>
 
|-
 
|<tex>R_{22}^{(1)}</tex>
 
|<tex>(0 + 1)^*</tex>
 
|}
 
<div style="clear:both;"></div>
 
 
Окончательное регулярное выражение, эквивалентное автомату, строится путем объединения всех тех выражений, для которых первое состояние
 
является начальным, а второе {{---}} заключительным.  В нашем примере <tex>1</tex> {{---}} начальное состояние, а <tex>2</tex> {{---}} заключительное, поэтому нам нужно лишь выражение <tex>R_{12}^{(1)}</tex>, равное <tex>1^*0(0 + 1)^*</tex>
 
 
Отметим, что первый вариант значительно короче. Для решения системы уравнений необходимо выполнить <tex>O(n)</tex> итераций, где <tex>n</tex> {{---}} число вершин. В каждом уравнении в худшем случае может быть <tex>|\Gamma| \cdot (n - 1)</tex> переменных в правой части {{---}} все возможные переходы по всем возможным состояниям. Теперь, для решения вторым вариантом, нам во-первых надо построить массив размера <tex>|\Gamma| \cdot n</tex> для всех переходов из всех состояний и выполнить столько же итераций, поскольку самый длинный путь в худшем случае будет проходить по всем переходам из всех вершин с возвращением в исходную, которая и будет являться терминальной, то есть в итоге сложность <tex>O((|\Gamma| \cdot n)^2)</tex>. Кроме того, в алгоритме на каждом шаге мы упрощали выражение, чтобы оно было более коротким. В общем случае длина выражения перед упрощением трудно поддается оценке, однако не стоит забывать про этот факт. В случае, если выражение не будет упрощаться, то по приведенной выше формуле итерации, оно, очевидно, с каждой итерацией будет значительно (степенная зависимость) расти.
 
 
== См. также ==
 
* [[Теорема Клини (совпадение классов автоматных и регулярных языков) | Теорема Клини]]
 
* [[Решение уравнений в регулярных выражениях | Решение уравнений в регулярных выражениях ]]
 
 
== Источники информации==
 
* [http://mathhelpplanet.com/static.php?p=teorema-klini Mathhelpplanet {{---}} Теорема Клини]
 
* [https://drona.csa.iisc.ernet.in/~deepakd/atc-2011/regular-exp.pdf Deepak D’Souza {{---}} Regular Expressions]
 
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. {{---}} М.: Издательский дом «Вильямс», 2008. {{---}} С. 112 {{---}} ISBN 978-5-8459-1347-0
 
 
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Автоматы и регулярные языки]]
 
[[Категория: Автоматы и регулярные языки]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: