Регулярные языки дискретная математика + видео обзор

Источник

Конечные автоматы и регулярные языки

В этом разделе мы начинаем изложение элементов теории формальных языков.

Говоря «формальный язык», мы имеем в виду то, что приведенные здесь результаты используются прежде всего при описании искусственных языков, придуманных людьми для специальных целей, например языков программирования. Но непреодолимой преграды между специально придуманными искусственными (формальными) языками и стихийно возникающими и развивающимися естественными языками не существует. Оказывается, что естественные языки характеризуются сложными грамматическими правилами, т.е. довольно жестко формализованы, а даже самый «научно разработанный» язык программирования содержит «темные места», однозначное понимание которых является проблемой.

Изучая языки, следует иметь в виду три основных аспекта.

Первый из них — синтаксис языка. Язык — это какое-то множество «слов», где «слово» есть определенная конечная последовательность «букв» — символов какого-то заранее фиксированного алфавита. Термины «буква» и «слово» могут пониматься по-разному (математическое определение этих терминов будет дано ниже). Так, «буквами» могут быть действительно буквы алфавита какого-нибудь естественного или формального языка, например русского языка или языка программирования «Паскаль». Тогда «словами» будут конечные последовательности «букв»: «крокодил», «integer». Такие слова называют «лексемами». Но «буквой» может быть «слово» («лексема») в целом. Тогда «слова» — это предложения естественного языка или программы языка программирования. Если фиксировано какое-то множество «букв», то не каждая их последовательность будет «словом», т.е. «лексемой» данного языка, а только такая последовательность, которая подчиняется определенным правилам. Слово «крыкадил» не является лексемой русского языка, а слово » iff » не является лексемой в «Паскале». Предложение «Я люблю ты» не является правильным предложением русского языка, точно так же, как и запись » x:==t » не есть правильно написанный оператор присваивания «Паскаля». Синтаксис языка и представляет собой систему правил, в соответствии с которыми можно строить «правильные» последовательности «букв». Каждое слово языка характеризуется определенной структурой, специфичной именно для данного языка. Тогда необходимо, с одной стороны, разработать механизмы перечисления, или порождения, слов с заданной структурой, а с другой — механизмы проверки того, что данное слово принадлежит данному языку. Прежде всего именно эти механизмы и изучает классическая теория формальных языков.

Слово «синтаксис» происходит от древнегреческих » syn » — «вместе» и » taxis » — «порядок, строй». Таким образом, синтаксис можно понимать как «составление».

Второй аспект — семантика языка. Семантика предполагает сопоставление словам языка некоего «смысла», «значения». Например, записывая математическую формулу, мы должны соблюдать определенные синтаксические правила (расстановка скобок, правописание символов, порядок символов и т.п.), но, кроме этого, формула имеет вполне определенный смысл, что-то обозначает.

От древнегреческих слов » sema » — «знак, знамение» и » semanticos » — » обозначающий «.

Язык — это средство общения, передачи информации. Если мы хотим, чтобы нас поняли, мы должны не только синтаксически правильно, соблюдая должный порядок букв в слове и слов в предложении, строить свою речь, но и заботиться об ее смысле, о тех идеях, которые мы выражаем в речи. Математические теории «смысла» появились сравнительно недавно, и мы очень коротко рассмотрим некоторые подходы к математическому описанию семантики языков программирования.

Наконец, третий аспект — прагматика языка. Прагматика связана с теми целями, которые ставит перед собой носитель языка: например, человек произносит речь, имея перед собой цели, связанные не с синтаксисом, не с семантикой языка, на котором он говорит или пишет, а, скажем, с получением за речь определенной суммы денег. Прагматика является уже скорее дисциплиной социально-философской, затрагивающей целеполагающую деятельность личности. Мы ни в малейшей степени не будем ее касаться.

От древнегреческих » pragma » — «дело, действие» и » pragmateia » — » деятельность «.

В этом разделе вначале будут рассмотрены основные понятия математической теории формальных языков, важнейшим среди которых является понятие порождающей грамматики, а затем — так называемые регулярные языки. Теория регулярных языков вместе с теорией конечных автоматов образует фундамент всей теории формальных языков.

Источник

Лемма о разрастании для регулярных языков

В теории формальных языков большое значение имеют утверждения, в которых формулируется необходимое условие принадлежности языка к тому или иному классу языков. Эти утверждения известны в литературе под названием лемм о разрастании (или лемм о «накачке»). С помощью этих лемм удается доказать, что тот или иной язык не является языком данного класса, например, не является регулярным, контекстно-свободным и т.п. Доказывать подобного рода «отрицательные» утверждения гораздо труднее, чем «положительные» (что язык есть язык данного класса ), ибо в последнем случае требуется придумать любую грамматику соответствующего класса, порождающую данный язык, а в первом нужно каким-то образом доказать, что не существует грамматики этого класса, порождающей язык. Применение лемм о разрастании состоит в следующем: доказав, что предлагаемый язык не удовлетворяет условию леммы о разрастании, мы можем быть уверены в том, что он заведомо не принадлежит соответствующему классу языков, и нам нечего и пытаться искать для него грамматику того же класса.

Мы рассмотрим подобного рода утверждения для классов регулярных, контекстно-свободных и линейных языков.

Начнем с леммы о разрастании для регулярных языков. Эта лемма (см. теорему 7.10) утверждает, что любой регулярный язык допускает представление всех своих достаточно длинных цепочек в виде соединения трех цепочек, причем средняя цепочка из этих трех не пуста, ограничена по длине, и ее «накачка» — повторение любое число раз — или выбрасывание не выводит за пределы языка (т.е. дает цепочки, принадлежащие данному регулярному языку).

2) контур, проходящий через ;

Примеры доказательств нерегулярности языка

Ясно, что накачка в этом случае выведет за пределы языка, так как при повторении цепочки число символов будет неограниченно расти, а число символов будет оставаться прежним.

Накачка невозможна по той же причине, что и в предыдущем случае.

Полезно иметь в виду следствие из леммы о разрастании.

Следствие 7.4. Если — бесконечный регулярный язык, то в нем найдется последовательность слов, длины которых образуют возрастающую арифметическую прогрессию.

В качестве такой последовательности можно взять последовательность слов из формулировки леммы о разрастании. Их длины образуют арифметическую прогрессию со знаменателем (длина «накачиваемой» средней подцепочки).

Отсюда легко получается вывод о том, что не являются регулярными следующие языки:

Можно доказать, что любой конечный язык регулярен и, более того, допускается конечным автоматом без контуров. Значит, последовательность цепочек, указанная в формулировке леммы, в таком случае не существует, но утверждение леммы остается истинным. Нужно всегда помнить простое логическое правило: утверждение вида «если А, то Б» равносильно утверждению вида «не А или Б».

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

Пример 7.13. Докажем нерегулярность языка правильных скобочных структур, порождаемых КС-грамматикой

Замечание 7.12. С использованием «техники пересечения» можно доказать нерегулярность языка из примера 7.12 следующим образом. Так как язык

нерегулярный, то и язык тоже не является регулярным.

Итак, можно вывести такой «рецепт»: если возникают существенные затруднения в доказательстве нерегулярности какого-либо языка с помощью только леммы о разрастании, то можно попытаться пересечь этот язык с некоторым регулярным языком так, чтобы нерегулярность пересечения легко доказывалась с использованием леммы о разрастании.

Источник

Видео

Построение регулярного выражения по конечному автомату и построение автомата по регулярному выражениСкачать

ДМ 1 курс - формальные языки - определения, регулярные языки, ДКАСкачать

Формальные языки и трансляции 1. Слова и языки. Конечные автоматыСкачать

Какие есть примеры регулярных языков? Душкин объяснитСкачать

Введение в теорию автоматов и вычислений. 1.8 пример автомата. язык автоматаСкачать

Что такое регулярные языки? Душкин объяснитСкачать

ДМ 1 курс - ДКА и регулярные языкиСкачать

Не бойтесь регулярных выражений. Regex за 20 минут!Скачать

ДМ 2 семестр 7 лекция: Языки. Регулярные выражения. Автоматы.Скачать

Практика по дискретной математикеСкачать