Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 129
Текст из файла (страница 129)
ОПРЕДЕЛЕНИЕ 17.5. Пусть А — алфавит. Выражением над А называется строка символов, которая представляет собой подмножество множества А'. Регулярное выражение состоит из символов *, 'и, Л, (, ) и а для каждого элемента а из А. Класс регулярных выражений определяется следующими правилами. !) Символ Л является регулярным выражением и для каждого а Е А символ а — регулярное выражение. В) Если юг и юз — регулярные выражения, то ю~юз, юг 'ч' и~а, ю,' и (ю~)— регулярные выражения. ш) Все регулярные выражения образуются по правилам (!) и (!!).
Каждому выражению сопоставляется множество согласно соответствию Х, определенному следующим образом; .Е(Л) = Л Х(а) = (а) для всех а Е А ~(н) = ц ~Г)=' ~(0=( ~0) =) РАЗДЕЛ 17.1. Регулярные языки 727 Поэтому г(аа') = (а) и (а)' .С(а(Ьис)д) = (а) о ((Ь) О (с)) о (д) г((а и'Ь)") = (а 0 Ь)' (а, аа, ааа, аааа, аааа,...); (аЫ, асд); (Л, а, Ь, аЬ, Ьа, аЬЬ, аЬа,...) = все строки, состоящие из 0 или более символов а и Ь; (ас, або, аЬЬс, аЬЬЬс,...); (а, Ь, с). Х(аЬ*с) = (а) о (Ь)" о (с) г(аЧЬЧс) = (а) О (Ь) О(с) Образ регулярного выражения является регулярным языком. Регулярные языки можно определить следующим образом. ОПРЕДЕЛЕНИЕ 17.6.
Класс В называется регулярным языком, если обладает следующими свойствами. !) Пустое слово, Л Е В, и если а Е А, то (а) е В. й) Если зт и зз Е В, то зз О зз, зз о зз, з) Е В. (и) Только множества, образованные согласно (!) и (й), принадлежат В. Хотя следующие утверждения здесь и не доказываются, но пересечение регулярных множеств является регулярным множеством и дополнение регулярного множества является регулярным множеством. ОПРЕДЕЛЕНИЕ 17.7. Пусть 5 и Т вЂ” подмножества множества А'.
Если 5 = Т, то 5 называется множеством, норозкденным множеством Т. ОПРЕДЕЛЕНИЕ 17.8. Пусть 5 и С вЂ” подмножества множества А*. Если 5 = С', то каждая строка в 5 может выражаться конкатенацией элементов множества С, и будем говорить, что С является кодом. Код С называется однозначно декодируемым, если каждую строку из 5 можно однозначно выразить конкатенацией элементов из С. Если множество 5 порождено множеством Т, то каждый элемент из множества 5 является конечной конкатенацией элементов множества Т.
Однако, элементы конкатенации, образующие данное слово, необязательно являются однозначно определимыми. Если Т = (а,Ь), то Т" состоит из пустого слова и всех возможных конечных строк из символов а и Ь. Если Т = (а, аЬ,Ь), то Т' = Т, но хотя каждая строка в Т' может выражаться единственным обоазом конкатенацией элементов из Т, это неверно для элементов множества Т, поскольку выражение аЬаЬ можно записать как (а)(Ь)(а)(Ь), а также как (аКЬ)(аЬ) и как (аЬ)(аЬ). 728 ГЛАВА 17.
Теория вычислений Поэтому (Ьа,аЬ,с), (аде,ддбее,г()с,дда) и (а,б,с,де) являются однозначно декодируемыми кодами, хотя (а,аб,бс,с), (аЬ,або,оде,де) и (а, Ьс,аЬс) однозначно декодируемыми не являются. ПРИМЕР 17.9. Функция на множестве о называется ретракционным отобразкением, или ретракцией, если г"ог' = г'. Образ при отображении )' называется ретрактом. Пусть  — ретракт при ретракционном отображении г": А — А'. Том Хэд (Тоги Неаб) показал, что ретракт порождается конечным кодом, обладающим таким свойством: каждое слово кода содержит элемент из А, который встречается в этом слове только один раз и не встречается ни в каком другом слове кода. Такие коды называются ключевыми кодами. Следовательно, (а, Ь,с), (а, Ье,се), (аде,дабее,саа) и (ад, Ьдае,седе) являются ключевыми кодами, порождающими ретракты, поскольку каждый из элементов а, Ь и с встречаются точно в одном слове и при этом только один раз.
Однако, (ба, аб, с), (аЬ, або, еде) и (а,аЬ,Ьс,д) тоже являются кодами, но не порождают ретракты. Пересечение ретрактов необязательно является ретрактом. На усмотрение читателя оставим доказательство, что пересечение множеств (ас, Ьс,д)" и (а,сб,сд)' порождено кодом, который можно описать выражением ас(Ьс)'д.
С) ОПРЕДЕЛЕНИЕ 17.10. Пусть А — алфавит. Код С С А' называется префиксным кодом, если для всех слов и, и е С; если и = ою для ю е А', то и = и и ш = Л. Это означает, что одно слово кода не может быть начальной строкой другого слова кода. Код С С А' называется суффиксным кодом, если для всех слов и, о Е С; если и = юо для ю Е А", то и = о и ю = Л.
Это означает, что одно слово кода не может быть конечной строкой другого слова кода. Множество (а,аЬ,ас) является кодом, но не является префиксным кодом, так как а является начальной строкой как для аЬ, так и для ас. Однако, данное множество — суффиксный код. Множество (а,Ьа,са) является префиксным кодом, ио суффиксным не является, поскольку а — конечная строка для Ьа и для са. Множество (ад,аЬ, ас) — одновременно префиксный и суффиксный код.
° УПРАЖНЕНИЯ 1. Найдите регулярные множества, соответствующие приведенным ниже выражениям. Если множество бесконечное, перечислите десять его элементов. а) а(Ьнснд)а; б) а Ь'с; в) (ачЬ)(сь'д); г) (аЪ'Л)Ч(сд)', д) а(Ьс)'с1. 2. Найдите регулярные множества, соответствующие приведенным ниже выражениям.
Если множество бесконечное, перечислите десять его элементов. а) Ьс(Ьс)', б) (ачЬ* ч' Л)(сча'); РяздЕЛ 17. а Регулярные языка 729 в) (ауЬснд)', г) (анЬ)(сад)Ь; д) а'(Ь~/с~/)б'. 3. Найдите регулярные выражения, соответствующие приведенным ниже регу- лярным множествам. а) (аб, ас, ад); б) (аЬ, ас, ЬЬ, Ьс); в) (а, аб, аЬЬ, аббЬ, аЬ66Ь,...); г) (аЬ,аЬаЬ,абабаЬ, аЬаЬабаЬ,аЬабабабаб,...); д) (аЬ, аЬЬ, ааб, ааЬ6). 4. Найдите регулярные выражения, соответствующие приведенным ниже регу- лярным множествам.
а) (аб,асб,ааб); б) (аЬ, абЬ, аЬЬЬ, аЬЬЬЬ,...); в) (ас(,ае,аХ,Ы,Ье,б|,сс(,се,сД; г) (абсс(, обабись, абсбсбЫ, абсбсбсбЫ,...); д) (абеб(, абе г", соса,сае1). 6. Пусть А = (а, Ь, с). а) Постройте регулярное выражение для множества всех элементов множества А", содержащих точно два символа Ь. б) Постройте регулярное выражение для множества всех элементов множества А', содержащих точно два символа 6 и два символа с. в) Постройте регулярное выражение для множества всех элементов множества А', содержащих точно два или более символов Ь. г) Постройте регулярное выражение для множества всех элементов множества А', которые начинаются и оканчиваются символом а и содержат, по крайней мере, один символ Ь и один символ с.
д) Постройте регулярное выражение для множества всех элементов множества А', которые состоят из одного или более символов а, за которым следует один или более символов 6, а затем один или более символов с. 6. Пусть А = (а,б). а) Постройте регулярное выражение для множества всех элементов множества А', содержащих в точности два символа б или в точности два си м вола а. б) Постройте регулярное выражение для множества всех элементов множества А', содержащих четное число символов Ь. в) Постройте регулярное выражение для множества всех элементов множества А', которые начинаются и оканчиваются символом а и содержат не менее одного символа 6.
г) Постройте регулярное выражение для множества всех элементов множества А' таких, что количество символов а в каждой строке кратно 3, а количество символов Ь кратно 5. ТЗ0 ГЛЯВЯ 17. Теория вычислений д) Постройте регулярное выражение для множества всех элементов множества А' таких, что длина каждой строки кратна 3. Какое из приведенных ниже выражений является однозначно декодируемым кодом? а) (аЬ, Ьа, а, Ь); б) (аЬ, асЬ,ассЬ,асссЬ,...); в) (а,Ь,с,Ы); г) (аЬ, Ьа, а); д) (а, аЬ, ас, ас().
8. Какие из приведенных ниже выражений описывают однозначно декодируе- мые коды? а) аЬ', б) аЬ''ч'Ьааа; в) аЪ'с и Ьааас; г) (а иЬ)(Ь'иа); д) (аи Ь и Л)(Ь |г аиЛ), 9. Какое из перечисленных ниже выражений является однозначно декодируе- мым кодом? Какое является суффиксным кодом? а) (а6, Ьа, ); б) (а6, аЬс, Ьс); в) (а,Ь,с, Ьп); г) (аЬа, Ьа,с); д) (аЬ, асЬ, ассЬ, асссЬ) 10. Какие из приведенных ниже выражений описывают префиксные коды? Какие из ннх описывают суффиксные коды? а) аЬ', б) аЬ'с; в) а"Ьс', г) (а и Ь)(Ь и а); д) аЬ.
11. Какие из приведенных ниже кодов являются однозначно декодируемыми? Обоснуйте свой ответ. а) 1110, 111, 1011, 11, 0101; б) 10,110,1110,0101; в) 010, 101, 0101, 1010, 10101; г) 0101,1001,011,11, 10011, 00101; д) 101,1001,10001,11011,11001,00111. 12. Какие из приведенных ниже кодов являются однозначно декодируемыми? Обоснуйте свой ответ. а) 110,1110,11110,111110,10; б) 1011,1010,1100,0101,0011,1100,1100,1111,0000; в) 101,010,11,10101,1011,1010; РАДЕЛ 17.2. Автоматы 731 г) 110,101,1001,11101,0101,0110,0111,10001; д) 11011,101,010100,11,1011,1110. 13.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
