Теорема Кліні

Головна теза Теореми Кліні : "Класи регулярних множин і автоматних мов співпадають ".

Доказ теореми Кліні

Будь граф переходів кінцевого автомата завжди можна представити у нормалізованої формі, в якій тільки одна початкова вершина тільки з вихідними ребрами і тільки одна заключна вершина тільки з вхідними ребрами.

Над графом переходів, представленим в нормалізованої формі, можуть бути виконані дві операції редукції - редукція ребра і редукція вершини - зі збереженням допускаемого цим графом переходів мови. Кожна операція редукції не змінює мови, распознаваемого графом переходів, але зменшує або число ребер, або число вершин.



Редукція ребра.png


Редукція вершіни.png


Отже, кожен автоматний мова є регулярним безліччю.
Для кожного регулярного виразу R може бути побудований кінцевий автомат (можливо недетермінірованний), що розпізнає мову, що задається R. Визначення таких автоматів дамо рекурсивно.


Теор2.png


Отже, кожне регулярне безліч є автоматним мовою. Теорема доведена.