Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)
Альтернативное доказательство
Теорема: |
Класс автоматных языков является подмножеством регулярных. |
Доказательство: |
Рассмотрим автоматный язык и ДКА для него. Для доказательства теоремы достаточно построить регулярное выражение, порождающее язык . Пусть наш автомат состоит из состояний, и состояние — стартовое. Также пусть — язык, состоящий из слов, которые приводят из состояния в терминальное.Заметим, что Заметим, что для всех и таких, что . Действительно, если по слову из состояния мы можем попасть в терминальное состояние, а между состояниями и есть переход по символу , то слово принаджелит языку . Также, если , то есть если стартовое состояние является и терминальным тоже, то добавим в сумму для и . . |