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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 8: Строка 8:
 
Рассмотрим автоматный язык <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 = \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>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> 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>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</tex>.

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

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

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

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