А.А. Вылиток - О регулярных языках (1115013), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

е.ошибка в цепочке)) и для каждой пары (p, a) ∈ K × Σ такой, что δ(p, a) не определена,положим δ(p, a) = ERR.Алгоритм моделирования работы ДКАВход: ДКА A = (K, Σ, δ, I, F) и цепочка x⊥, где x ∈ Σ*, ⊥ ∉ Σ — маркер концацепочки.Выход: «Да», если x ∈ L(A), иначе — «Нет».Метод: Введем переменные St для хранения текущего состояния автомата и cдля хранения очередного считанного символа входной цепочки x.beginc := первый символ цепочки x;St := I; {начальное состояние}while ( St ≠ ERR and c ≠ '⊥' )beginSt := δ (St, c);c := очередной символend;if St ∈ F thenwrite ('Да')elsewrite ('Нет')end;Покажем, что класс регулярных языков является собственным подклассомкласса контекстно-свободных языков (т.е.

языков, порождаемых грамматиками типа 2).Для этого достаточно найти КС-язык, который не является регулярным.Утверждение. Контекстно-свободный язык L = {a nb n | n ≥ 1} нерегулярен.Доказательство (от противного). Предположим, что язык L регулярен. Тогдасуществует конечный автомат A = ( K , Σ, δ , I , F ) , допускающий язык L : L( A) = L .(Напомним, что любой регулярный язык может быть задан конечным автоматом).Пусть число состояний автомата A равно k (k > 0). Рассмотрим цепочку a k b k ∈ L .

Таккак L = L(A) , a k b k ∈ L( A) . Это означает, что в автомате A есть успешный путь T спометкой a k b k :aaaabbbbp1 ⎯⎯→p2 ⎯⎯→L⎯⎯→pk ⎯⎯→pk +1 ⎯⎯→pk + 2 ⎯⎯→L ⎯⎯→p2 k ⎯⎯→p2 k +1 ,где pi ∈ K для i = 1,K,2k + 1 . Так как в автомате A всего k состояний, среди p1, p2, …,pk + 1 найдутся хотя бы два одинаковых. Иными словами, существуют i, j, 1 ≤ i < j ≤ k,aaтакие что pi = pj. Таким образом, участок pi ⎯⎯→L⎯⎯→p j пути T является циклом.Пусть длина этого цикла равна l (l > 0, так как цикл — это непустой путь).

Рассмотримуспешный путь T ′, который отличается от T тем, что циклический участокaapi ⎯⎯→L⎯⎯→p j присутствует в нем дважды:aaaaaabp1 ⎯⎯→L pi ⎯⎯→L⎯⎯→( pi = p j ) ⎯⎯→L⎯⎯→pj ⎯⎯→L pk +1 ⎯⎯→L p2 k +1Пометкой пути T ′ является цепочка a k +l b k . Поскольку T ′ — успешный путь,a k + l b k ∈ L( A) . Так какa k +l b k ∉ L , получаем, чтоL ≠ L( A) . Это противоречитравенству L = L( A) . Следовательно, предположение о том, что L регулярен, неверно.

Характеристики

Список файлов учебной работы