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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



Определение 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* формулируется теорема о классификации автоматных языков по их сложности, измеряемой звездной высотой (необходимой глубиной вложенности итераций при задании данного языка регулярным выражением).



Поделиться:


Последнее изменение этой страницы: 2021-04-04; просмотров: 90; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.198.146.224 (0.006 с.)