XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 73
Текст из файла (страница 73)
Такие слова называют „лексемами". Но „буквой" может быть „слово" („ лексема" ) в целом. Тогда „слова" — зто предложения естественного языка или программы языка программирования. Ес- ли фиксировано какое-то множество „букв", то не каждая их последовательность будет „словом", т.е. „лексемой" данного языка, а только такая последовательность, которая подчиняется определенным правилам. Слово екрыкадил" не является лексемой русского языка, а слово „зй" не является лексемой в „Паскале". Предложение еЯ люблю ты" не является правильным предложением русского языка, точно так же, как и запись „х:= =Ф" не есть правильно написанный оператор присваивания „Паскаля".
Синтаксис' языка и представляет собой систему правил, в соответствии с которыми можно строить „правильные" последовательности „букв". Каждое слово языка характеризуется определенной структурой, специфичной именно для данного языка. Тогда необходимо, с одной стороны, разработать механизмы перечисления, или порождения, слов с заданной структурой, а с другой — механизмы проверки того, что данное слово принадлежит данному языку. Прежде всего именно эти механизмы и изучает классическая теория формальных языков.
Второй аспект — седесзмоииш лзымп. Семантика" предполагает сопоставление словам языка некоего „смысла", езначения". Например, записывая математическую формулу, мы должны соблюдать определенные синтаксические правила (расстановка скобок, правописание символов, порядок символов и т.п.), но, кроме этого, формула имеет вполне определенный смысл, что.то обозначает. Язык — это средство общения, передачи информации.
Если мы хотим, чтобы нас поняли, мы должны не только синтаксически правильно, соблюдал должный порядок букв в слове и слов в предложении, строить свою речь, но и заботиться об ее смысле, о тех идеях, которые мы выражаем в речи. Математические 'Слово „сиитаксис" происходит от древиегреческих „еуп" — „вместе" и „Сззпе" — „порлдок, строй". Таким образом, синтаксис можно понимать как „составление".
"От древкегреческюс сюв „леша" — „знак, зиамеиие" и „еешапС!сое"— „обозкачаквпий". 462 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ теории „смысла" появились сравнительно недавно, и в дополнении Д.8.2 к следующей главе мы очень коротко рассмотрим некоторые подходы к математическому описанию семантики языков программирования.
Наконец, третий аспект — крагматаика лэыка. Прагматика' связана с теми целями, которые ставит перед собой носитель языка; например, человек произносит речь, имея перед собой цели, связанные не с синтаксисом, не с семантикой языка, на котором он говорит или пишет, а, скажем, с получением за речь определенной суммы денег. Прагматика является уже скорее дисциплиной социально. философской, затрагивающей целеполагающую деятельность личности. Мы ни в малейшей степени не будем ее касаться.
В этой главе вначале будут рассмотрены основные понятия математической теории формальных языков, важнеишим среди которых является понятие порождающей грамматики, а затем — так называемые регулярные языки. Теория регулярных языков вместе с теорией конечных автоматов образует фундамент всей теории формальных языков. 7.1. Алфавит, слово, язык Рассмотрим самое простое понятие теории языков — понятие алфавита.
Алуеаеит — это произвольное непустое конечное множество т' = (ам..., а„~, элеменшы которого называют 6уквами или сцмволамк. Обычно задают определенную нумерацию алфавита (как, скажем, для русского алфавита: еа" — первая буква, „б"— вторэя и т.д. до 33-й — ея"). Впредь договоримся, фиксируя алфавит, записывать его буквы в порядке их номеров. "От древнегреческих „ргвяюе" — „деве, действие" и „ргвишаее!в"— „девтелъиость".
463 7.1. Албвевт, сюво, еэык Определение 7.1. Словом или цепочкой в алфавите У называют произвольный кортеж из множества У" (б-й декар1воеой с1пепекв алфавита У) для различных й = 0,1,2,... Например, если У = (а, Ь, с), то (а), (Ь), (с), (а, Ь), (а, Ь, с), (с, Ь, а, а, с) и т.д. есть слова в У. При й = 0 получаем пус1пой корп1еж, называемый в данном контексте пус1пык словом или пустой цепочкой и обозначаемый Л.
Множество всех слов в алфавите У обозначают У', а множество всех непустых слов в У вЂ” как У+. Слова, ра ди удобства чтения и простоты записи, будем записывать беэ скобок и запятых (ср. с записями кортежей в 1,2). Так, для записанных вьппе слов получим: а, Ь, с, аЬ, або, сбаас. Такая запись слова согласуется с его интуитивным понима вием как цепочки следующих друг за другом симвоюв. Тогда пустое слово — это слово, не имеющее символов, „пустой лист бумаги", на котором еще ничего не написано. По определению, длцка слова 1е — число компонент кортежа, т.е.
если 1е Е У", то длина слова 1е равна г. Длину слова е договоримся обозначать ~ю~. Ясно, что для пустого слова ~Л! = О. Длину сюва тем самым можно понимать как число составляющих это слово букв. Докажем, что множество У' счетно. Для этого достаточно построить какую-либо нумерацию этого множества. Рассмотрим здесь нумерацию, называемую лексикографцческой. В данной нумерации пустому слову присваивается номер О, а буквам а1, ..., а„алфавита У вЂ” номера 1, ..., и соответственно.
Если сюво х имеет лексикографический номер 1е, то слову ха; присваивается номер Ы, +1. Отсюда следует, что лекснкографический номер слова а;,а;,... а; будет равен 11+и 12+ ° "+бе. Заметим, что последняя сумма напоминает запись числа в системе счисления по модулю и (мо1цности алфавита) с тем лишь различием, что используется цифра и, но не допускается 464 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ цифра О. Итак, по любому слову в алфавите т" однозначно вычисляется его лексикографический номер. Обратно, любое натуральное число однозначно раскладывается по степеням и указанным выше образом. Действительно, если дано число Ж, то при 0 < Ф ( п оно служит номером пустого слова (1т' = 0) нли некоторой буквы алфавита.
Иначе представим Ф в виде Ф = Й1т4+те, где 1<те(п. Если Й1 < и, то Ф есть номер слова аь, а„,. Иначе раскладываем Й1 в виде Й1 Й2п+ т1> где 1 < т1 ( т4. Тогда Ф = Й2п +т1п+те. С числом Й2 поступаем точно так же, как и с Й1. После конечного числа шагов получим разложение числа Ф в виде т~в+ и тш-1+ ° ° ° + 1и 1+те~ где каждое число т; 10 < 4 ( тп) находится в диапазоне от 1 до и.
По полученному разложению Ф однозначно восстанавливается слово в т', имеющее номер Ж: ат ат ~ ° ° ° от~ отр. Пример 7.1. Вычислим номер слова сЬаас в алфавите 1а, Ь,с). Имеем 34 ° 3+ Зз 2+ 32 1+ 31 1+ 3 279 Решим обратную задачу, найдя слово в данном трехбуквенном алфавите, имеющее номер 321. 465 7.1. Алфавит, сюво, лэые Согласно приведенному вьппе алгоритму, получим 321 = 106. 3+ 3 = (35 3+ 1) 3+ 3 = 11.3+2)3 +1.3+3 Зо 3 3+2)Зз+2 3 +1.3+3.3 = 3 ° 3 -1- 2 ° Зз + 2 3 .!. 1 ° 3 .!.
3 Следовательно, искомое слово есть сббас. Лексикографическая нумерация напоминает способ упорядочения слов в словарях: однобуквенные слова следуют в порядке номеров букв в алфавите, среди двух двухбуквенных слов меньший номер имеет слово, начинающееся буквой с меньшим номером, и т.д. Но полного совпадения нет, так как в словаре слова группируются по начальной букве, а не по длине. Нам будет удобно в даяьнейшем использовать следующую запись непустого слова х в алфавите У по буквам: х = х(1) х(2)... х(к), где х(1), 1 < 1 < к, — 1-я буква опона х. Определение 7.2..Языком в а вфавипзе У называется произвольное подмножество множества т'*.
Множество всех языков в алфавите т', т.е. множество 2У, есть булеан счетного множества, и, следовательно, оно в силу теоремы 1.15 Кантора имеет мои!ностпь континуума. Наша следующая задача — определить на множестве 2к всех языков в произвольном (но фиксированном!) алфавите !' алгебраическую спзруктпуру. На множестве 2К можно определять различные операции. Прежде всего языки — зто множества, следовательно, над ними можно производить все те же операции, что и над множествами: обьединение, пересечение, раэностпь, дополнение и т.п. Универсальное мнохеестпво в данном случае есть множество слов У", которое называют универсальным языком.
466 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ Кроме перечисленных теоретико-множественных операций можно рассматривать и специальные операции над языками. Прежде чем обратиться к этим операциям, определим операцию соединения (или конкагпенации) слое. Соединением слов х = х(1)х(2)...х(я) и у = у(1)у(2)... у(т) называют слово ху = х(1)х(2)...х(й)у(1)у(2)...у(гп). По определению, считаем хЛ = Лх = х для любого х. Соединение иногда обозначают точкой (. ). Неформально соединение ху получается приписыванием слова у справа к слову х.
Таким образом, для любых двух слов х ч У~ и у е У~ конкатенация ху е У~~~ (й, т > 0). Следовательно, ~ху~ = ф+ ~у~. Из определения также следует, что соединение слов ассоциативно, т.е. для произвольных трех слов х, у, х имеет место х(ух) = (ху)х, и поэтому — с учетом написанного вьппе свойства пустого слова — множество У" всех слов в алфавите У с операцией соединения образует моноид (У',, Л).
Единица моноида — пустое слово. Этот моноид есть не что иное, как свободный моноид, порожденный алфавитом У (см. пример 2.7). Для него используют то же обозначение, что и для самого множества всех слов в алфавите У, т.е. У'. На основе понятия соединения слов определим понятие вхождения одного слова в другое. Определение 7.3. Вхождение с,лова х е У' в слово у Е У' — зто упорядоченная тройка слов (и, х, о), такая, что у = ихо.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
