Мастихина А.А. Формальные языки и автоматы, для РК-6

МГТУ им. Н.Э.БауманаФакультет «Фундаментальные науки»Кафедра «Высшая математика»Мастихина А.А.Формальные языки и автоматыпод редакцией Р.С.ИсмагиловаЭлектронное учебное изданиеМетодические указания к выполнению домашнего задания подискретной математикеМоскваc 2011 МГТУ им. Н.Э.БауманаУДК 518.5Рецензент:- кандидат физ.-мат. наук Алексей Иванович БелоусовМастихина А.А.Формальные языки и автоматы: Методические указания к выполнению домашнего задания по дискретной математике. – М, МГТУ им. Н.ЭБаумана, 2011. – 23 с.Изложены основные теоретические сведения из теории формальныхязыков и конечных автоматов. Разобраны примеры решения типовыхзадач. Содержит условия типового расчета.Для студентов, изучающих дискретную математику.Одобрено учебно-методической комиссией НУК "Фундаментальныенауки"МГТУ им.

Н.Э.БауманаМастихина Анна АнтоновнаФОРМАЛЬНЫЕ ЯЗЫКИ И АВТОМАТЫ:МЕТОДИЧЕСКИЕ УКАЗАНИЯК ВЫПОЛНЕНИЮ ДОМАШНЕГО ЗАДАНИЯ ПО ДИСКРЕТНОЙМАТЕМАТИКЕc 2011 МГТУ им. Н.Э.Баумана11Предварительные сведения.Данное пособие опирается на некоторые сведения из теории графов. Введем необходимые определения.Ориентированный псевдограф G — это пара множеств (V, E), где V —множество вершин, E — множество ребер, причем каждому ребру e ∈ Eсоответствует упорядоченная пара вершин (v, u), v, u ∈ V ( ребро ведетиз v в u). Возможны петли (v = u) и кратные ребра (несколько ребердля одной пары вершин).

Геометрически ориентированный псевдографизображается так: для каждой вершины изображается точка на плоскости, а для каждого ребра (v, u) - линия, направленная от вершины v квершине u, причем разным ребрам соответствуют разные линии.Путь в ориентированном псевдографе — последовательность реберe1 , e2 , ..., ek , таких что ребро ei ведет от vi к vi+1 . Говорят, что такой путьведет из v1 в vk+1 .Вершина v достижима из вершины u, если существует путь, ведущийu из в v.2Регулярные языки.Возьмем некоторое конечное множество символов A, назовем его алфавитом, а его элементы — буквами.Словом в данном алфавите называется конечная цепочка букв этогоалфавита.Буквы будем обозначать a, a1 , a2 , ..., b, b1 , ..., а слова — α, β, ..., причемα = a(1)a(2)...a(n), где α(i) — i-тая буква слова α.Длиной слова α называется число букв в данном слове: |α| = n.

Например, |abbbc| = 5.Введем также пустое слово Λ как слово нулевой длины: |Λ| = 0.Слово β называется подсловом слова α, если найдутся слова α1 и α2 ,необязательно непустые, что α = α1 βα2 . Например, подсловами словаabc является само abc, а также a, b, c, ab и bc.Множество всех возможных слов в алфавите A обозначим A∗ .Языком в данном алфавите A называется любое подмножество L множества всех слов A∗ , L ⊂ A∗ .Пример. A = {a, b, c}L = {Λ, aa, abc, cb, bc}.

A∗ — все слова, которые можно составить избукв a, b, c: Λ, a, b, c, aa, ab, ac, ba,...Операции над языками. Регулярные языки.2Рассмотрим произвольный алфавит A и всевозможные языки в нем.Определим следующие операции.1) Объединением языков L1 и L2 называется множество слов, входящих хотя бы в один из этих языков: L = L1 ∨ L2 = {α|α ∈ L1 илиα ∈ L2 }.2) Конкатенацией (произведением) языков L1 и L2 называется множество слов вида L1 · L2 = {αβ, где α ∈ L1 , β ∈ L2 }. Таким образом, этослова, получающиеся приписыванием к каждому слову из L1 слова изL2 . Конкатенация слов α и β есть слово αβ.Например, пусть L1 = {a, ab, b}, L2 = {b, ca}.

ТогдаL1 ∨ L2 = {a, ab, b, ca}, L1 · L2 = {ab, abb, bb, aca, abca, bca}В частности, L... · L} обозначается как Lk и есть {α1 ...αk |αi ∈ L, i =| · {zk1...k}.Например, L = {a, bb}, L2 = {aa, abb, bba, bbbb}Рассмотрим произвольный язык L и пустое слово Λ. По определениюΛ · L = L, L · Λ = L.В качестве языка можно рассматривать и пустое множество слов.Выполнено:L·∅=∅=∅·LL∨∅=L3) Итерацией языка L называется язык вида Λ ∨ L ∨ L2 ∨ ... ∨ Li ∨ ...,он обозначается L∗ .Например, в алфавите A = {a, b} итерация языка L = {a2 , ab} будетL∗ = {Λ, a2 , ab, a4 , abab, a3 b, ab2 a, a6 , a5 b, aba4 , ...}.Для L = {a2 } итерация такова: L∗ = {Λ, a2 , a4 , a6 , ...}.Множество всех слов в алфавите A = {a1 , ..., ar } получается итерацией объединения его букв: A∗ = (a1 ∨ ... ∨ ar )∗ .Язык называется регулярным, если его можно получить из простейших языков {Λ}, {a}, a ∈ A, с помощью этих трех операций за конечноечисло шагов.Формальное определение.1) ∅ — регулярный язык, {Λ} — регулярный язык, {a}, a ∈ A, —регулярный язык.2) Пусть L1 , L2 — регулярные языки.

Тогда языки L1 · L2 , L1 ∨ L2 иL∗1 также регулярны.3) Других регулярных языков нет.Выражение, задающее регулярный язык, называется регулярным выражением. Для простейших языков эти выражения — ∅, Λ, a, остальныесоставляются из простейших с помощью ∨, ·,∗ и скобок.3Задача. Составить регулярное выражение для языка в алфавите{a, b, c}, состоящее из всех слов, начинающихся на ab, но не заканчивающихся на c.Как уже было сказано, множество всех слов в алфавите A = {a, b, c}есть A∗ = (a ∨ b ∨ c)∗ .Все слова, начинающиеся на ab — конкатенация ab со множествомвсех слов.

Выражение для такого языка есть ab(a ∨ b ∨ c)∗ . Слово незаканчивается на букву c, значит, оно заканчивается на a или на b.Поэтому регулярное выражение для данного языка имеет вид ab(a ∨b ∨ c)∗ (a ∨ b).Задача. Составить регулярное выражение для языка в алфавите{a, b, c} из всех слов, где буква b встречается только в виде массива bn ,где n — четное число.Сначала зададим массив bn .

Это (bb)∗ , кстати, сюда входит и пустоеслово (случай n = 0). Слова языка — всевозможные последовательностибукв a, c и таких массивов.Искомое регулярное выражение — (a ∨ (bb)∗ ∨ c)∗ .Но не все формальные языки являются регулярными.Пример нерегулярного языка.Рассмотрим алфавит A = {a}. Тогда язык, состоящий из слов, длинакоторых — квадрат некоторого натурального числа, будет нерегулярным. L = {ak |k = n2 , n ∈ N }3Источники и языки.Пусть зафиксирован некоторый алфавит A. Возьмем ориентированныйпсевдограф, некоторым ребрам которого приписаны буквы из алфавита A. Ребра без букв назовем пустыми. Выделим некоторое множествовершин, называемых начальными и множество вершин, называемых заключительными. Такая конструкция называется источником.Начальные вершины обозначаются ∗, а заключительные — y.Рассмотрим путь e1 , ..., ek в источнике.

Выпишем последовательнобуквы, приписанные ребрам e1 , ..., ek . Получившееся слово назовем словом, порожденным данным путем. Если все ребра пути пустые, то такойпуть порождает пустое слово.Каждому источнику ставится в соответствие язык L ⊂ A∗ следующим образом. Для каждого пути из некоторой начальной вершины внекоторую заключительную выписывается порожденное им слово. Всетакие слова, и только они составляют язык L.

Говорят, что источникпорождает язык L.4Пример.∗a --ab-yb?L = a2 b∗ ∨ abb∗ ∨ b∗-Чтобы проверить, что данный источник порождает именно этот язык,нужно рассмотреть все пути, ведущие из начальной вершины в заключительную.Первая теорема Клини.Каждый язык, порождаемый источником, является регулярным.Для доказательства будет полезна лемма об источниках.kПусть вершины источника пронумерованы. И пусть Rijобозначаетмножество всех слов, порожденных путями в данном источнике из вершины с номером i в вершину с номером j, не проходящими вершину сномером больше k. Следующая лемма иллюстрирует "понижение степе0k.и позволяет таким образом перейти к простейшим языкам Rijни" RijЛемма.Выполнены следующие равенства.k−1k−1k−1 ∗ k−1k1)Rij= Rij∨ Rik(Rkk) Rkjk−1 ∗ k−1k2)Rkj = (Rkk ) Rkjk−1k−1 ∗k3)Rik= Rik(Rkk)k−1 ∗k4)Rkk= (Rkk)Доказательство леммы.Докажем первое равенство. Для этого рассмотрим множество путей,ведущих из вершины i в вершину j и не проходящих вершину с номеромбольшим, чем k ( но саму вершину k проходить можно).

Таким образом,kвсе пути, слова на которых составляют Rij, могут либо вовсе не проходить вершину k, либо проходить ее некоторое количество раз. В первомk−1случае слова на всех таких путях по определению составляют язык Rij.Во втором случае каждый такой путь можно поделить на части: путь довершины k, несколько путей, выходящих из k и возвращающихся в нее,и путь из k в j, причем во всех этих путях вершина k может встречатьсятолько в начале и в конце. Таким образом, множество слов, порожденноеk−1k−1 ∗ k−1) Rkj . Поэтомуэтими путями, можно описать выражением Rik(Rkkk−1k−1k−1 ∗ k−1kRij = Rij ∨ Rik (Rkk ) Rkj .

Первое равенство доказано.Пункты 2) − 4) следуют из 1). Выведем пункт 2).k−1 ∗ k−1k−1k−1k= (Λ ∨Пусть i = k. Тогда Rkj= Rkj∨ Rkk(Rkk) Rkjk−1 ∗k−1k−1 ∗k−1k−1Rkk (Rkk ) )Rkj = (Rkk ) )Rkj . Остальные пункты выводятся аналогично.5Доказательство теоремы.Составим регулярное выражение для языка, порожденного произвольным источником.Итак, рассмотрим источник И с n вершинами. Некоторым образомперенумеруем его вершины. Множество начальных вершин обозначим I,а множество заключительных — F .nОчевидно, что вырабатываемое им множество слов есть ∨i∈I,k∈F Rlk,это слова, порожденные путями от начальных вершин к заключительным, которые не проходят вершины с номерами, большими, чем количеnприменяем лемму до тех пор, покаство вершин.

Далее, для каждого Rlk0в ней не будут участвовать лишь Rij , то есть слова, соответствующиемножествам путей из вершины i в вершину j, не заходящих ни в какуюдругую вершину. Можно выписать конкретные выражения для каждого0Rijследующим образом.0= ∅, если нет ребер, ведущих из вершины i в вершину j, причемRiji 6= j.0Rij= a1 ∨ ... ∨ ak , если из i в j ведут ребра с буквами a1 , ..., ak . Еслиот i к j ведет еще и пустое ребро, то в объединение добавляется пустоеслово Λ.0= Λ, если есть только пустое ребро.RijМножество Rii0 также всегда содержит пустое слово Λ.0kЯсно, что языки Rijрегулярны.