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

Материал из Викиконспекты
Версия от 20:53, 3 октября 2015; Dmitriy D. (обсуждение | вклад) (Исправил неправильное доказательство. Кто-нибудь проверьте меня.)
Перейти к: навигация, поиск
Теорема (Клини):
Классы автоматных и регулярных языков совпадают.
Доказательство:
[math]\triangleright[/math]
Автоматы для регулярных языков нулевого поколения
Автомат для объединения двух регулярных языков
Автомат для конкатенации двух регулярных языков
Автомат для замыкания Клини регулярного языка

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

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

База. [math]n = 0[/math]. Для этого достаточно построить автоматы для трех языков:

  • [math]L = \varnothing[/math],
  • [math]L = \left\{\varepsilon \right\}[/math],
  • [math]L = \left\{c \right\}[/math].

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

  • [math]L^\prime = L \cup M[/math],
  • [math]L^\prime = LM[/math],
  • [math]L^\prime = L^*[/math].

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

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

2. [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].

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

  • [math]\xi_{ii0} = (c_1 \mid \dots \mid c_l)^*[/math] , где [math]c_1, c_2, \dots c_l[/math] символы, по которым есть переход из состояния [math]i[/math] в него же самого.
  • [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].
  • [math]\xi_{iik} = (\xi_{ii{k-1}} \mid \xi_{ik{k-1}} (\xi_{kk{k-1}})^* \xi_{ki{k-1}} )^*[/math].
  • [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]