Теорема Клини (совпадение классов автоматных и регулярных языков)

Материал из Викиконспекты
Перейти к: навигация, поиск
НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.
Теорема (Клини):
Классы автоматных и регулярных языков совпадают.
Доказательство:
[math]\triangleright[/math]
Автоматы для регулярных языков нулевого поколения
Автомат для объединения двух регулярных языков
Автомат для конкатенации двух регулярных языков
Автомат для замыкания Клини регулярного языка
  • [math]\mathrm{REG} \subseteq \mathrm{AUT}[/math].

Для доказательства будем строить автоматы, допускающие регулярные языки (см. картинки справа). При этом будем использовать индукцию по номеру поколения регулярного языка.

База

[math]n = 0[/math].
Для этого достаточно построить автоматы для трех языков:
  1. [math]L = \varnothing[/math],
  2. [math]L = \left\{\varepsilon \right\}[/math],
  3. [math]L = \left\{c \right\}[/math].

Индукционный переход

Умеем строить автоматы для языков [math]n[/math]-ого поколения. Будем строить для [math]n + 1[/math].
Для этого достаточно научиться строить автоматы для следующих языков ([math]L, M \in \mathrm{R_n}[/math]):
  1. [math]L^\prime = L \cup M[/math],
  2. [math]L^\prime = LM[/math],
  3. [math]L^\prime = L^*[/math].

Заметим, что по предположению индукции автоматы для [math]L, M[/math] могут быть построены.

Итого, мы можем по регулярному выражению построить автомат, допускающий тот же язык.


  • [math]\mathrm{AUT} \subseteq \mathrm{REG}[/math].

Для доказательства будем строить регулярное выражение, допускающее язык, заданный каким-то автоматом. Пусть задан автомат [math]A[/math] с набором состояний [math]Q = \left\{1, 2, \dots n \right\}[/math].

Определим регулярные выражения, задающие следующие множества слов:

[math]\xi_{ijk} = \left\{ s \mid \langle i,s \rangle \vdash^* \langle j, \varepsilon \rangle \right\} [/math], причем в качестве промежуточных вершин выступают только такие, у которых номер не более [math]k[/math].


Построим эти регулярные выражения:

  1. [math]\xi_{ii0} = (c_1 \mid \dots \mid c_l)^*[/math] , где [math]c_1, c_2, \dots c_l[/math] символы, по которым есть переход из состояния [math]i[/math] в него же самого.
  2. [math]\xi_{ij0} = c_1 \mid \dots \mid c_l[/math], где [math]c_1, c_2, \dots c_l[/math] символы, по которым есть переход из состояния [math]i[/math] в состояние [math]j[/math].
  3. [math]\xi_{iik} = (\xi_{ii{k-1}} \mid \xi_{ik{k-1}} (\xi_{kk{k-1}})^* \xi_{ki{k-1}} )^*[/math].
  4. [math]\xi_{ijk} = \xi_{ij{k-1}} \mid \xi_{ik{k-1}} (\xi_{kk{k-1}})^* \xi_{kj{k-1}}[/math].


Теперь нетрудно задать регулярное выражение для всего языка:

[math]\varphi = \xi_{s{t_1}n} \mid \xi_{s{t_2}n} \mid \dots \mid \xi_{s{t_r}n}[/math], где [math]s[/math] — стартовое состояние, а [math]t_1, t_2, \dots t_r[/math] — терминальные состояния исходного автомата.
Таким образом, мы построили по автомату регулярное выражение, допускающее тот же самый язык.
[math]\triangleleft[/math]

См. также

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

  • Википедия — Теорема Клини
  • Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 61.— ISBN 5-8459-0261-4
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_Клини_(совпадение_классов_автоматных_и_регулярных_языков)&oldid=82837»