Длины слов в автоматных языках

↑

▷ Содержание

⇐ ПредыдущаяСтр 5 из 21Следующая ⇒

Определение 4.3.1. Пусть , и . Множество называется заключительно периодическим (ultimately periodic) с периодом m, если выполнено условие

Лемма 4.3.2. Пусть . Тогда равносильны следующие утверждения:

1. множество является заключительно периодическим;

2. найдутся такие положительное целое число m и конечные множества и , что

3. множество является объединением конечного семейства арифметических прогрессий.

Теорема 4.3.3. Язык L над однобуквенным алфавитом {a} является автоматным тогда и только тогда, когда множество является заключительно периодическим.

Доказательство. Для доказательства необходимости достаточно рассмотреть детерминированный конечный автомат, распознающий язык L.

Теорема 4.3.4. Если язык L является автоматным, то множество является заключительно периодическим.

Доказательство. Рассмотрим конечный автомат, распознающий язык L. Заменим все символы в метках переходов на символ a. Осталось применить теорему 4.3.3 к полученному автоматному языку над однобуквенным алфавитом {a}.

До сих пор мы рассматривали два способа конечного описания формального языка: грамматики и автоматы. Третий способ, часто наиболее удобный и компактный, - регулярные выражения. В них используются символы, обозначающие итерацию, конкатенацию и объединение языков. Например, для обозначения итерации традиционно используется символ "звездочка".

Регулярные выражения находят практическое применение во многих компьютерных приложениях, таких как текстовые редакторы и интерпретаторы командной строки. В автоматических генераторах лексических анализаторов принято использовать именно регулярные выражения в качестве формализма, с помощью которого задаются классы однотипных лексем (например, класс идентификаторов, класс десятичных констант). В языках программирования Perl, Python и др. имеется встроенная поддержка регулярных выражений.

В начале лекции даются необходимые определения. Затем в разделе 5.2* приводятся некоторые тождества регулярных выражений, такие как ассоциативность конкатенации, дистрибутивность конкатенации относительно объединения и др. В разделе 5.3 доказывается, что регулярные выражения задают в точности класс автоматных языков. В разделе 5.4* формулируется теорема о классификации автоматных языков по их сложности, измеряемой звездной высотой (необходимой глубиной вложенности итераций при задании данного языка регулярным выражением).

Познавательные статьи:



Формы дистанционного обучения

Передача мяча двумя руками снизу

Значение правильной осанки для жизнедеятельности человека

Основные ошибки при выполнении передач мяча на месте