Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 130
Текст из файла (страница 130)
Какие из приведенных ниже кодов являются префиксными кодами? а) 101,1101,0101,001,1001,11101,0110,01001; б) 1101, 0011, 1010, 1110, 1010, 0101, 1100, 1111; в) 101,1100,01010,10101,0011,0110; г) 1011,10101,10110,0101,01100,111000; д) 1101,10001,1001,01110,10110,110110. 14. Какие коды в упражнении ! являются префиксными кодами? 15. Какие коды в упражнении 2 являются префиксными кодами? 16. а) Какие коды в упражнении 1 являются суффиксными кодами? б) Какие коды в упражнении 2 являются суффиксными кодами? в) Какие коды в упражнении 3 являются суффиксными кодами? 17. Код называется инфиксным кодом, если никакая строка кода не является подстрокой другой строки кода. Всегда ли суффиксный и префиксный коды являются инфиксными кодами? Докажите или постройте контрпример. 18.
Всегда ли инфиксный код является префиксным и суффиксным кодом одновременно? Докажите или постройте контрпример. 19. Какие коды в упражнении 1 являются инфиксными кодами? 20. Какие коды в упражнении 2 являются инфиксными кодами? 21. Какие коды в упражнении 3 являются инфиксными кодами? 22. Существует ли префиксный код, состоящий из слов длины 1,2,3,3? 23.
Существует ли префиксный код, состоящий из слов длины 1, 3, 3, 3, 4, 5, 5, 5? 24. Существует ли инфиксный код, состоящий из слов длины 1,3,3,3? 25. Докажите, что ключевой код является префиксным и суффиксным кодом одновременно. 17.2. АВТОМАТЫ По сути, автомат представляет собой устройство, распознающее, воспринимающее или допускающее определенные элементы множества А', где А — конечный алфавит.
Различные автоматы (совокупность автоматов) распознают или допускают различные элементы множества А'. Подмножество элементов множества А, допускаемое автоматом М,— это язык, который называется языком над алфавитом А, допускаемым автоматом М, и обозначается М(Ь). Для заданного конечного алфавита автомат состоит из множества Я вЂ” множества состояний и функции с: А х д — Я, называемой функцией переходов. Множество Я содержит элемент зо и одно или более финальных состояний.
Автомат М обозначается через (А,Я,зо,Т,Г), где А — алфавит, Я вЂ” множество состояний, зо — начальное или исходное состояние, Т вЂ” множество финальных состояний и à — функция перехода. Обратите внимание, что входом для с является буква из А и состояние, принадлежащее множеству Я. Выходом является 732 ГЛАВА З7.
Теория вычислений состояние из Я (возможно, то же самое состояние). Если автомат находится в состоянии з и "читает" букву а, то (и, з) является входом для с, и Р'(и, з) — следующее состояние. Для автомата в качестве "начала" можно рассматривать начальное состояние зо. Если автомат "читает" букву а алфавита А, то он "переходит" в состояние з = Е(а,зо). Если теперь автомат "читает" букву из А, например, Ь, то он переходит в состояние з' = Р'(и,з). Следовательно, по мере "прочтения" букв алфавита автомат переходит из одного состояния в другое. Пусть М вЂ” автомат с алфавитом А = (и,Ь), множеством состояний Я = (зо,з,,зз), а функция Ь' задана таблицей ео Предположим, что М "читает" букву и, за которой следуют буквы Ь и а. Поскольку автомат начинает функционировать в состоянии ео, и буква, которую он читает, это а, то Г(а, зо) = зы поэтому теперь автомат находится в состоянии зы Следующей буквой для чтения является Ь и Г(Ь,зг) = зз.
Наконец, читается последняя буква и, и так как Г(а, зз) = ез, автомат остается в состоянии ез. Функцию перехода Г можно задать также совокупностью правил. Такой автомат лучше всего изображать графически с помощью диаграммы состояний, являющейся ориентированным графом, у которого состояния представлены вершинами, а ориентированное ребро из вершины з в вершину е' помечено буквой из алфавита А, например, буквой а, если Р'(и,з) = з'. Направленная стрелка, помеченная буквой а, будет называться а-стрелкой. Поэтому приведенный выше автомат можно представить графически, как показано на рис. 17.1. (Отметим, что хотя диаграмма состояний на рис.
17.1 и является ориентированным графом, тем не менее, исходя из условий задания некоторых автоматов, соответсвующие диаграммы могут не быть ориентированными графами, поскольку из одного состояния в другое может вести не одно ориентированное ребро. Если Если Если Если Если Если автомат находится в состоянии зо автомат находится в состоянии з| автомат находится в состоянии зз автомат находится в состоянии зо автомат находится в состоянии з1 автомат находится в состоянии ез и читает а, то он переходит в состояние з1 и читает и, то он переходит в состояние з, и читает а, то он переходит в состояние зз и читает Ь, то он переходит в состояние зь и читает Ь, то он переходит в состояние зз и читает Ь, то он переходит в состояние з1 РДЗЦЕЛ 17.2. Явтоматы 733 Более точным названием таких диаграмм является мулыпиграфы, или помеченные орграфы.
Слово или строку ива~аз...а„ из А" автомат "читает" следуюшим образом: сначала читается ао, затем аг и так до тех пор, пока не будет прочитано а„. Как отмечалось выше, некоторые состояния определены как финальные состояния. Автомат допускает или распознает строку, аоа!аз ... а„, если после прочтения а„ он останавливается в финальном состоянии. Если з — начальное состояние, то соответствуюшая вершина обозначается схемой, изображенной на рис.
17.2. Если з — финальное состояние, то соответствуюшая вершина обозначается, как изображена на рис. 17.3. Рис. 17.3 Рис. 17.2 Например, для автомата, диаграмма состояний которого изображена на рис.!7А, состояние зо — начальное, а состояние зз — финальное. Рис. 17.4 Автомат допускает слово Ьаа, поскольку после прочтения Ь он переходит в состояние зз; после прочтения а — в состояние з,; после прочтения второго а, он переходит в состояние зз, которое является финальным состоянием.
Можно убедиться, что автомат допускает также слова аЬЬЬа и 6Ь, но не распознает слова ЬЬЬ, аЬаЬ или аЬЬ. Как отмечалось выше, множество слов, допускаемых автоматом, назывется языком, допускаемым автоматом. ПРИМЕР 17.11. Рассмотрим автомат с диаграммой состояний, изображенной на рис. 17.5. Очевидно, что автомат допускает слово 66. Для слова а в каждом состоянии имеется петля, поэтому при чтении а состояние не меняется, что дает возможность до прочтения следуюшего слова Ь читать любое необходимое количество 734 ГЛАВА 17, Теория вычислении слов а. Таким образом, автомат читает ааЬаЬааа, 6ааЬаЬ, ЬаааЬ, ЬаЬааа, ааЬааЬаа и может фактически прочесть любое слово языка, заданного регулярным выражением а"Ьа"Ьа'. Поскольку А = (а,Ь), то такой язык можно описать также как множество всех слов, содержащих точно два 6. Состояние з4 является примером состояния зацикливания.
Попав в состояние зацикливания, автомат никогда не сможет из него выйти. а ПРИМЕР 17.12. Рассмотрим автомат с диаграммой состояния, изображенной на рис. 17.6 (упрощенный вид — на рис. 17.7). Рис. /7.6 Рис. /7.7 Автомат допускает, очевидно, только слова аЬ и ас. Этот язык можно задать с помощью регулярного выражения а(Ь'/с). П ПРИМЕР 17.13. Рассмотрим автомат с диаграммой состояний, изображенной на рис. 17.8. а,Ьс Рис. /7.8 Каждое слово следует начинать с аЬ и заканчивать на с. Однако петлю аабс можно повторять требуемое количество раз, поскольку она начинается и заканчивается в аз.
Поэтому регулярным выражением для этого автомата будет аЬс(ааЬс)". С) ПРИМЕР 17.14. Рассмотрим автомат с диаграммой состояний, изображенной на рнс. 17.9. Рис. /7.9 Ь Ь Ь,с -Π— 'О ~О а~ е)ь а,Ь,с РАЗДЕЛ 17.2. Автоматы 735 Автомат при чтении трех последовательных Ь переходит в состояние вз, которое является состоянием зацикливания. Это единственный способ попасть в состояние вз, и все другие состояния являются финальными состояниями.
Таким образом, язык, который допускает автомат, состоит из всх слов, не включаюших три последовательных Ь. П Рассмотренные автоматы часто называются детерминированными автоматами, так как в любом состоянии и для любого значения из алфавита, которое подается в автомат для чтения, существует одно и только одно состояние. Иными словами, такая ситуация обусловлена тем, что Г: А х Я вЂ” о является функцией.
Зачастую удобно ослабить правила таким образом, чтобы л была не функцией, а отношением. Если опять рассмотреть Г как множество правил для а Е А и з Е Я, то могут существовать правила, предоставляющие возможность перехода из данного состояния в некоторые другие состояния, или такие правила не могут существовать. В последнем случае автомат, как говорят, "зависает" и не может далее функционировать. Автоматы, для которых Р не обязательно является функцией, называются недетерминированными автоматами. Рассмотрим, например, приведенную ниже диаграмму состояний, изображенную на рис. 17.10.
Если в состоянии зо прочитывется слово, символ а, то автомат переходит в состояние з, или зз. Однако, если автомат находится в состоянии зг и прочитывается слово, символ Ь, то автомат "зависает", поскольку нет Ь-стрелки, выходяшей из состояния з,. Отметим, что в соответствии с приведенным выше определением множество детерминированных автоматов принаждлежит множеству недетерминированных автоматов. ПРИМЕР 17.15. Легко убедиться, что автомат с диаграммой состояний, изображенной на рис.
!7.11, допускает язык, задаваемый регулярным выражением аЬ'с. ПРИМЕР 17.16. Автомат с диаграммой состояний, изображенной на рис. 17.12, допускает язык, задаваемый регулярным выражением аНЬ. .,З О р .17.7г 736 ГЛАВА 17. 7еария вычислений ПРИМЕР 17.17. Автомат с диаграммой состояний, изображенной на рис. 17.!3, допускает язык, задаваемый регулярным выражением аа"ЬЬ'. Яа ДЬ вЂ” О-'О-'~О Рис. 17.13 ПРИМЕР 17.18. Автомат с диаграммой состояний, изображенной на рис. 17.14, допускает язык, состоящий их строк, содержаших не менее двух символов а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
