Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 71
Текст из файла (страница 71)
Таким телом может быть только ВА или ВС. Просмотрев грамматику, находим, что с такими телами там есть только продукции А — > ВА и 5 — » ВС. Таким образом, две головы, А и В, образуют Хы. Рис. 7.!4 Табяица дяя цепочки ЬааЬа построенная аягоритиом Кока-Янгера-Косами В качестве более сложного примера рассмотрим вычисление Хьп Цепочку ааЬ в позициях с 2 по 4 можно разбить, заканчивая первую подцепочку в 2 или в 3, т.е. в определении Хм можно выбрать»с = 2 или 7е = 3, Таким образом, нужно рассмотреть все тела в ХхХ»»() Х»»Х»». Этим множеством цепочек является (А, С)(В, С) О (В)(В) = (АВ, АС, СВ, СС, ВВ).
Из пяти цепочек этого множества только СС является телом; его голова — В. Таким образом, Хг» = (В). С3 7.4.5. Обзор неразрешимых проблем КС-языков В следующих главах излагается замечательная теория, позволяющая доказать формально, что существуют проблемы, которые нельзя разрешить никаким алгоритмом„выполняемым на компьютере. Используем ее для того, чтобы показать, что многие элементарные вопросы о грамматиках и КС-языках не имеют алгоритма решения; они называются "неразрешимыми проблемами". Сейчас же ограничимся следующим списком наиболее значительных неразрешимых вопросов о контекстно-свободных грамматиках и языках. ГЛАВА 7.
СВОЙСТВА КОНТВКСТНО-СВОБОДНЫХ ЯЗЫКОВ 314 1. Неоднозначна ли данная КС-грамматика 6? 2. Является ли данный КС-язык существенно неоднозначным? 3. Пусто ли пересечение двух КС-языков? 4. Равны ли два данных КС-языка? 5. Равен ли Х данный КС-язык, где Х вЂ” алфавит этого языка? Отметим, что вопрос 1 о неоднозначности отличается от остальных тем, что это вопрос о грамматике, а не о языке.
Все остальные вопросы предполагают, что язык представлен грамматикой или МП-автоматом, но это все равно вопросы о языке (или языках). Например, в противоположность вопросу 1 вопрос 2 требует по данной грамматике 6 (яли МП-автомату) определить, существует ли некоторая эквивалентная ей однозначная грамматика 6'. Если 6 сама по себе однозначна, то ответом, безусловно, будет "да", но если 6 неоднозначна, то для языка грамматики С может существовать другая грамматика 6; которая однозначна, как было с грамматиками выражений в примере 5.27.
7.4.6. Чпражнения к разделу 7.4 7.4.1. Постройте алгоритмы разрешения следующих проблем: а) (я) конечен ли язык Ц6) данной грамматики 6? Указание. Используйте лемму о накачке; б) (!) определить, содержит ли язык Ц6) данной грамматики С не менее 100 цепочек; в) (1!) по данной грамматике 6 и ее переменной А определить, существует ли выводимая цепочка, которая начинается символом А. Указание. Напомним, что переменная А может впервые появиться в середине некоторой выводимой цепочки, а затем все символы слева от нее могут породить д 7.4.2. Используйте технику, описанную в разделе 7.4.3, для построения линейных по времени алгоритмов разрешения следующих вопросов о КС-грамматиках.
1. Какие символы встречаются в выводимых цепочках? 2. Какие символы являются вчэорождающими? 7.4.3. Примените С э'К-алгоритм к грамматике 6 из примера 7.34, чтобы определить, принадлежат ли Цб) следующие цепочки: а) (е) аЬаЬа; б) ЬаааЬ; в) иаЬаЬ. 7.4.4. (ч) Покажите, что для любой НФХ-грамматики все деревья разбора цепочек длиной л имеют 2п — 1 внутренних узлов (отмеченных переменными). 7,4. СВОЙСТВА РАЗРЕШИМОСТИ КС-ЯЗЫКОВ 7.4.5. (?) Измените СтК-алгоритм так, чтобы он сообщал, сколько различных деревьев вывода у данной цепочки, а не просто, принадлежит ли она языку грамматики. Резюме Удаление бесполезных символов.
Переменную можно удалить из КС-грамматики, если она не порождает ни одной терминальной цепочки или не встречается в цепочках, выводимых из стартового символа. Для корректного удаления таких бес- полезных символов нужно сначала проверить, порождает ли каждая переменная терминальную цепочку, и удалить те, которые не порождают. Только после этого удаляются переменные, которые не выводятся из стартового символа. Удаление цетгых и е-продукций.
По данной КС-грамматике С можно найти еще одну КС-грамматику, которая порождает тот же язык, за исключением цепочки е, но не содержит цепных продукций (с единственной переменной в качестве тела) и е-продукций (с телом е). Нормальная форма Хамского. По данной КС-грамматике б можно найти еще одну КС-грамматику, которая порождает тот же язык, за исключением цепочки ц и находится в нормальной форме Хомского: нет бесполезных символов, и тело каждой продукции состоит либо из двух переменных, либо из одного терминала. Лемма о накичке. В любой достаточно длинной цепочке КС-языка можно найти короткую надцепочку, два конца которой можно синхронно "накачивать", т.е повторять произвольное число раз.
Хотя бы одна из накачиваемых цепочек не равна е. Эта лемма, а также ее более мощная версия, которая называется леммой Огдена н приводится в упражнении 7.2.3, лают возможность доказывать, что многие языки не являются контекстно-свободными. Операции, сохраняющие контекстно-свободные языки. КС-языки замкнуты относительно подстановки, объединения, конкатенации, замыкания ( ), обращения и обратного гомоморфизма. КС-языки не замкнуты относительно пересечения и дополнения, но пересечение КС-языка с регулярным всегда является КС-языком. Проверка пустоты КС-языка. Существует алгоритм, который по данной грамматике О определяет, порождает ли она какие-нибудь цепочки.
Аккуратная реа- лизация этой проверки выполняется за время, прямо пропорциональное размеру самой грамматики. Проверка принадлежности КС-языку. Алгоритм Кока-Янгера-Касами определяет, принадлежит ли данная цепочка данному КС-языку. Если язык зафиксирован, эта проверка требует времени 0(п'), где п — длина проверяемой цепочки.
ГЛАВА 7. СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ Литература Нормальная форма Хамского впервые описана в [2), нормальная форма Грейбах — в [4), хотя конструкция, описанная в упражнении 7.1.11, принадлежит Полу (М. С. Ранй). Многие фундаментальные свойства контекстно-свободных языков установлены в [1). Среди инх лемма о накачке, основные свойства замкнутости, а также проверки для простых вопросов, таких как пустота и конечность КС-языка. Результаты о незамкнутости относительно пересечения и дополнения происходят из работы [6), а дополнительные результаты о замкнутости, включая замкнутость КС-языков относительно обратного гомомарфнзма, — из [3). Лемма Огдена предложена в [5). Алгоритм Кока-Янгера-Касами имеет три независимых источника.
Работа Кока распространялась частным образом и не была опубликована. Версия по сути того же алгоритма, записанная Касами, появилась только в закрытом докладе Воздушных Сил СГН. И лишь работа Янгера была опубликована в [7). 1. У. Ваг-НИ!е1, М. Рег[ез, апг) Е. Я|апцг, "Оп (от|па! ргорегйез о! я|пр1е рЬгаяе-ягпсшге 8гапнпагз*', х. Р!юпегнь 5ргас)|и ив Коггнлип!7гаг!ат!аггс)ь 14 (1961), рр. 143 — 172. 2.
[Ч.СЬошз[гу, "Оп сегга|п (отша! ргореп|ся о(8|анппагз", гп7аилайоп аг|г! Саги|.о! 2;2 (1959), рр. 137-167. (Хомский Н. О некоторых формальных свойствах грамматик,— Кибернетический сборник, вып. 5. — Мз ИЛ, 1962. — С 279 — 311.) 3, 8. О!пяЬнг8 ап|1 О. Козе, "Орегабопв зч[йсЬ ргезегче г!ейпаЬ|!!гу |и!апйнайея*', !. АСМ 10:2 (1963), рр. 175-195. (Гинзбург С., Роуз Дж.
Об инвариантности классов языков относительно некоторых преобразований. — Кибернетический сборник, Новая серия, вып. 5. — Мл Мир, 1968. — С. 138 — ! 66.) 4. Б. Оге!Ьасй, "А печг пот|па[-!ог|п гйеогегп (ог сопсехг-ггее рЬ|аье яггисшге 8гапипагз'*, 2 АСМ 12: 1 (1965), рр. 42-52. 5.
)ч'. 08|)еп, "А Ье!р(и[ геяз1| (ог ргочш8 !пЬегепг ашЬ!Ен!гу", Маг)|ел|аггел! 5уггепм ТЬеогу 2:3 (1969), рр, 31-42. (Огден У. Результат, полезный для доказательства сушественной неоднозначности. — сб. "Языки и автоматы". — Мл Мнр, 1975. — С. ! 09 — ! 13.) б. 8. Бойе!пЬег8, "Мосе оп гйе Ьоо1еап ргорегйез о( сопгехг-ггее !апйна8ез", !л!аггпалоп ап|! Сап|го! 3:4 (1960), рр.
372 — 375. 7. [). Н. Уопп8ег, "Весо8п!г!оп апд рагяп8 о! сопгехг-!гее!ап8найез !и гнпе и ",!п!от|||абаи а|к! Сопла! 10:2 (1967), рр. 189-208. (Янгер Д. Распознавание и анализ контекстно-свободных языков за время п'. — Сб. "Проблемы математической логики".— Мс Мир, 1970.
— С. 344 — 362.) ЛИТЕРАТУРА 317 ГЛАВА 8 Введение в теорию машин Тьюринга В этой главе направление наших усилий меняется. До снх пор нас интересовали в основвом простые классы языков н пути нх использования для относительно ограниченных задач, вроде аналнза протоколов, поиска в текстах нлн синтаксического анализа. Теперь начнется исследование языков, которые вообще можно определить с помощью вычислительных устройств.
Это равносильно изучению того, что может компьютер, поскольку распознаванне цепочек языка является формальным способом выражения любой задачи, а решение задачи — зто разумное представление того, что делает компьютер. Мы предполагаем, что читатель знаком с программированием на языке С. Вначале, используя зто знание, с помощью неформальных доводов покажем, что существуют определенные задачи (проблемы), которые с помощью компьютера решить невозможво. Этн залачн называются "неразрешимыми". Затем познакомимся с классической формальной моделью компьютера, которая называется машиной Тьюринга (МТ). И хотя машины Тьюринга совершенно не похожи на компьютеры, н было бы весьма неэффективно нх производить н продавать, тем не менее машина Тьюрннга получила признание как точная модель того, что способно делать любое физическое вычислительное устройство, В главе 9 машина Тьюринга используется для развития теории "неразрешимых" проблем, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
