Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 131
Текст из файла (страница 131)
"'3я-Я-® Рис. 17.14 Преимушество недетерминированных автоматов состоит в том, что нет необходимости включать в них несущественные ребра. Поэтому в некоторых дальнейших построениях будет намного проше использовать недетерминированные автоматы. Любой язык, который допускается детерминированным автоматом, очевидно, допускается и недетерминированным автоматом, так как множество недетерминированных автоматов включает в себя множество детерминированных автоматов. Следующая теорема показывает, что любой язык, который допускается недетерминированным автоматом, допускается и детерминированным автоматом. ТЕОРЕМА 17.19.
Для каждого недетерминированного автомата существует эквивалентный детерминированный автомат, который допускает тот же язык. Вместо формального доказательства продемонстрируем построение детерминированного автомата, который допускает язык, допускаемый недетерминированным автоматом. Пусть Я вЂ” множество состояний недетерминированного автомата.
Используем элементы Р(Я), т.е, элементы подмножества множества Я в качестве состояний для создаваемого детерминированного автомата. Рассмотрим недетерминированный автомат Аг, изображенный на рис. 17.15. Яа ДЬ - О-'О-'~О Рис. 17.15 Пусть (ео) — начальное состояние. Построим а-стрелку из (зо) во множество всех таких состояний, что сушествует о-стрелка из ео в это состояние. В данном случае имеется а-стрелка из зо в зо и а-стрелка из зо в зы т.е.
построена а-стРелка из (зо) в 1зо,з,). Не сУществУет Ь-стРелки из зо в любое дРУгое состоЯние, поэтомУ стРоим Ь-стРелкУ из 1зо) в пУстое множество О. ТепеРь РассмотРим состоЯние 1зо, зг). СтРоим а-стРелкУ из (зо, з,) во множество всех таких состояний, что сушествует а-стрелка либо из зо, либо из в, в это состояние. В данном случае строим и-стрелку из (зо,з~) в самое себя.
Строим Ь-стрелку из РАЗДЕЛ 17.2. Автоматы 737 1зо. э~) во множество всех таких состояний, что существует Ь-стрелка из зо или из в~ в это состояние. В данном случае строим Ь-стрелку из !во, вг) в 1зз). Поскольку не существует ни а-стрелки, ни 6-стрелки из любого состояния в пустом множестве ни в какое другое состояние, строим а-стрелку и Ь-стрелку из пустого множества в себя. Теперь рассмотрим 1вз). Поскольку не существует а-стрелки из вз ни в какое другое состояние, строим а-стрелку из (вз) в пустое множество. Учитывая, что только 6-стрелка ведет из вз в себя, строим Ь-стрелку из )вз) в себя.
Финальное состояние (состояния) состоит из всех множеств, содержащих элемент финального множества автомата !У. В данном случае (вз) — единственное финальное состояние. Итак, построена диаграмма состояний, изображенная на рис. 17.!6, которая является диаграммой состояний детерминированного автомата. Этот автомат допускает тот же язык, что и автомат !У, а именно, язык, заданный выражением а'аЬЬ". Рис. !7.16 В общем случае имеется следующая процедура для построения детерминированного автоматата из недетерминированного. 1. Начать из состоЯниЯ 1во), где во — начальное состоЯние недетеРминиРованного автомата. 2. Для каждого а, Е А построить агстрелку из (во) во множество всех состояний таким образом, что имеется а;-стрелка из во в это состояние.
3. Для каждого вновь построенного состояния Я и для каждого а, е А построить а,-стрелку из Яу во множество всех таких состояний, что существует а,-стрелка из элемента множества Я в это состояние. 4. Продолжать процесс, пока есть возможность создавать новые состояния. 5. Преобразовать все множества состояний Яу, содержащие элемент финального множества недетерминированного автомата, в финальное состояние. ПРИМЕР 17.20. Построим детерминированный автомат, соответствующий неде- терминированному автомату, изображенному на рис. !7.17.
738 ГЛАВА 17. Теория вычислений Поскольку имеется а-стрелка из зо в зы строим а-стрелку из (зо) в (зг). Так как не существует Ь-стрелки из зо в любое иное состояние, строим Ь-стрелку из зо в пустое множество И. Имеется а-стрелка из з, в зз, поэтому строим а-стрелку из (з~) в 1зз). Поскольку имеется Ь-стрелка из зг в ео и из з, в зз, строим Ь-стРелкУ из (з~) в 1ео,ез). СтРелок из ез в дРУгое состоЯние не сУществУет, поэтому строим а-стрелку и Ь-стрелку из зз в пустое множество.
Имеются а- стрелки из зо в зы из зз в з~ и из зз в зз, поэтому строим а-стрелку из (зо,зз) в (зы зз). Не существует Ь-стрелок ни из состояния зо, ни из состояния зз, поэтому строим Ь-стрелку из 1зо, зз) в пустое множество. Так как имеется а-стрелка из з~ в зз, строим а-стрелку из (зыаз) в (зз) Имеются 6-стрелки из зг в зо и из з~ в зз, поэтомУ стРоим 6-стРелкУ из (зы ез) в 1зо, зз). Этим завеРшаетсЯ постРоение детерминированного автомата, изображенного на рис. 17.!8.
Проведенное нами исследование регулярных языков и автоматов подытоживает следующая теорема, которая приводится без доказательства. ТЕОРЕМА 17.21. (Кпмии) Язык является регулярным тогда и только тогда, когда он допускается автоматом. ° УПРАЖНЕНИЯ 1. Какие из перечисленных ниже слов допускаются автоматом, изображенным на рис. 1?.19? а) аЬ6а б) ааЬЬЬ в) Ьабаб г) аааЬЬЬ д) ЬЬааЬ РАЗДЕЛ ~7.2. Автоматы 739 2. Какие из перечисленных ниже слов допускаются автоматом, изображенным на рис. 17.20? а) ааа66 б) аЬЬЬа666 в) ЬаЬаЬа г) аааЬаЬ д) 6ЬЬаЬаЬ а 3.
Составьте выражение для языка, который допускается автоматом, изобра- женным на рис. 17.21. 4. Составьте выражение для языка, который допускается автоматом, изобра- женным на рис. 17.22. Риа /7.21 5. Составьте выражение для языка, который допускается автоматом, изобра- женным на рис. 1?.23. 6. Составьте выражение для языка, который допускается автоматом, изобра- женным на рис. 17.24.
7. Найдите детерминированный автомат, который допускает язык, заданный выражением аа*ЬЬ'сс'. РАЗДЕЛ 17.3. Грамматики 741 17.3. ГРАММАТИКИ Таким образом, продукция для первого из приведенных выше примеров имеет вид: агИ- А+В А- О В- О А- 1 А- 2  — 1  — 2 В- 9 А- 9 Если добавить правило, состоящее в то продукции будут иметь вид: агИ вЂ” ~ А+ В А — О том, что А можно заменить на А + В, А- А+В В- О В- 1 В- 2 А- 1 А — 2 А — ~9 В- 9 Формально грамматика определяется следующим образом. Грамматика — это совокупность правил, которые используются для построения языка.
Правила позволяют заменять символы или строки символов другими символами или строками символов. Допустим, имеется начальное слово адд, которое можно заменить на А + В, а А и В можно заменить любым неотрицательным целым числом, меньшим 10. Пользуясь этим правилом, А можно заменить на 3 и  — на 2, получив 3+ 2. Если А заменить на 5, а  — на 6, то получим 5+ 6. При вводе дополнительного правила о возможности замены А на А + В появится возможность начать с замены агИ на А+ В. Если после этого заменить А на А+В, получим А+В+В.
Заметим следующее; поскольку А можно заменить как на А+ В, так и на целое число, то при замене символов однозначности не требуется. Кроме того, и одно, и второе В в выражении А+ В+В не обязательно заменять одним и тем же значением. Если А заменить на 3, первое В заменить на 5, а второе  — на 7, то получим 3+ 5+ 7. С другой стороны, можно снова было бы заменить А на А+ В, получить А + В + В + В и продолжать строить суммы произвольной длины. Отметим, что в приведенных выше правилах символы адд, А и В можно заменять другими символами, в то время как символ + и целые числа заменять нельзя.
Символы, которые можно заменять другими символами, называются нетерминальными символами, а символы, которые нельзя заменять другими символами, называются терминальными символами. Правила, указывающие, как заменять символы, называются продукциями. Обозначим продукцию (или правило), смысл которой состоит в том, что агИ можно заменить на А ч- В, через а~И вЂ” А+ В.
742 ГПЯВЯ 17. Теория вычислений ОПРЕДЕЛЕНИЕ 17.22. Формальная грамматика, или грамматика неаосредстаеннык составляющих состоит из конечного множества нетерминальных символов Х, конечного множества терминальных символов Т, элемента В Е дг, называемого начальным символом, и конечного множества продукций Р, которое является отношением в (йг 0 Т)', таким что каждый первый элемент упорядоченной пары из Р содержит символ из Х и, по крайней мере, один первый элемент некоторого правила является начальным элементом В. Если И' и И" — элементы из (йГ 0 Т)', И' = иош, И" = ио'ш, а о — о'— продукция, то непосредственный вывод И" из И' обозначается И' ~ Иг'.
Если для п > О, то говорят, что И'„ выводится из Игы Обозначается это следующим образом: И'г =ь'„ И'„. Формальная грамматика Г обозначается четверкой ()т', Т, В, Р). Множество всех строк элементов из Т, которые можно породить с помощью множества продукций Р, называется языком, порождаемым грамматикой Г, и обозначается Г(Т,). При порождении слова в грамматике Г для вывода новых строк продолжаем использовать продукции до тех пор, пока не получим строку, содержащую только терминальные элементы. Таким образом, для последнего из приведенных выше примеров имеем: )У = (аЫ, А, В), Т = (+,0,1,2,3,4,5,6,7,8,9), В = а<Ы Р = ((айй, А+В), (А, А+В), (А, О), (А, 1),..., (А, 9), (В, О), (В, 1),..., (В, 9) ), где (агЫ,А+ В) обозначено через а<Ы вЂ” А+ В, (А, А+ В) обозначено через А — А+ В и т.д.
Язык, порожденный грамматикой Г, — это множество всех формальных выражений конечных сумм неотрицательных целых чисел, меньших, чем 10. ПРИааЕР17.23. В описанной выше грамматике выведем выражение 3+2+4. Начнем с продукции а~Ы вЂ” ~ А+ В, чтобы вывести А+ В. Затем применим продукцию А- А+В, чтобы вывести А+ В+ В. РАЗМЕЛ 17.3. Грамматики 743 Далее применим продукции А — ~3  — ~2  — >4, чтобы вывести +2+ 4. ПРИМЕР 17.24.
Пусть требуется построить грамматику, позволяющую вывести арифметические выражения для множества целых чисел (0,1,2,3,4,5,6,7,8,9). Язык, порожденный этой грамматикой, есть множество всех конечных арифметических выражений для множества целых чисел (0,1,2,3,4,5,6,7,8,9). Примерами служат выражения 3 х (5 + 4) и (4+ 5) сь (3 2), где символ " обозначает показатель степени. Понятно, что желательно исключить такие выражения, как 3+ х6 и 3+ +6 х 4 — 5. Пусть множество М = (В,А, В) и Т = (+, —, х,+, ",0,1,2,3,4,5,6,7,8,9,(,)).
Нам понадобятся следующие продукции: А — 9  — 0  — 9 Используем грамматику для вывода арифметического выражения ((2+3) х (4+5)). Начнем с продукции В- (А х В). Затем применим продукции А- (А+В) В- (А+В), ((А + В) х (А+ В)) . чтобы получить Продукции А — ~2 и  — ~3 дают ((2+3) х (А+ В)). Наконец, применим продукции А- 4 и В- 5,  — (А+ В)  — (А — В)  — ~ (АхВ)  — (А-:В)  — (А В) А — (А+ В) А — (А — В) А — (А х В) А — (А сь В) А — (А"В) В В В В В А (А+ В) (А — В) (А х В) (А гь В) (А" В) 0 744 ГЛАВА 17, Теория вычислений чтобы вывести ((2 + 3) х (4 + 5)) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
