dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 42
Текст из файла (страница 42)
В их числе объединение, конкатенация, замыкание (итерация), пересечение, дополнение, разность, обращение, гомоморфизм (замена каждого символасоответствующей цепочкой) и обратный гомоморфизм.♦ Проверка пустоты регулярного языка. Существует алгоритм, который по такомузаданному представлению регулярного языка, как автомат или регулярное выражение, определяет, является ли представленный язык пустым множеством.♦ Проверка принадлежности регулярному языку.
Существует алгоритм, который позаданной цепочке и некоторому представлению регулярного языка определяет,принадлежит ли цепочка языку.♦ Проверка различимости состояний. Два состояния некоторого ДКА различимы,если существует входная цепочка, которая переводит в допускающее только одноиз этих состояний. Если начать с того, что все пары, состоящие из допускающегои недопускающего состояний, различимы, и найти дополнительные пары, которыепо одному символу переходят в различимые состояния, можно обнаружить всепары различимых состояний.♦ Минимизация детерминированных конечных автоматов. Состояния любого ДКАможно разбить на группы взаимно неразличимых состояний. Состояния из двухразных групп всегда различимы. Если заменить каждую группу одним состоянием, получим эквивалентный ДКА с наименьшим числом состояний.ËèòåðàòóðàЗа исключением очевидных свойств замкнутости регулярных выражений (относительнообъединения, конкатенации и итерации), которые были доказаны Клини [6], почти все результаты свойств замкнутости воспроизводят аналогичные результаты, полученные дляконтекстно-свободных языков (этому классу языков посвящены следующие главы).
Такимобразом, лемма о накачке для регулярных языков является упрощением соответствующегорезультата для контекстно-свободных языков (Бар-Хиллел, Перлес и Шамир [1]). Из результатов этой работы следуют некоторые другие свойства замкнутости, представленные вданной главе, а замкнутость относительно обратного гомоморфизма обоснована в [2].ÐÅÇÞÌÅСтр. 183183Операция деления (см.
упражнение 4.2.2) представлена в [3]. В этой работе обсуждаетсяболее общая операция, в которой вместо одиночных символов находятся регулярные языки.Ряд операций “частичного удаления”, начиная с упражнения 4.2.8, в котором говорилось опервых половинах цепочек регулярного языка, был определен в [8]. Сейферас и Мак-Нотон[9] изучили общий случай, когда операция удаления сохраняет регулярность языков.Алгоритмы разрешения, такие как проверка пустоты и конечности регулярных языков, а также проверка принадлежности к регулярному языку, берут свое начало в [7].
Алгоритмы минимизации числа состояний ДКА появились в [5]. В работе [4] предложеннаиболее эффективный алгоритм нахождения минимального ДКА.1.Y. Bar-Hillel, M. Perles, and E. Shamir, “On formal properties of simple phrase-structuregrammars,” Z. Phonetik. Spachwiss. Kommunikations-forsch. 14 (1961), pp. 143–172.2.S.
Ginsburg and G. Rose, “Operations which preserve definability in languages,” J. ACM10:2 (1963), pp. 175–195. (Гинзбург С., Роуз Дж. Об инвариантности классов языковотносительно некоторых преобразований. — Кибернетический сборник, Новая серия, вып. 5. — М.: Мир, 1968. — С. 138–166.)3.S.
Ginsburg and E. H. Spanier, “Quotients of context-free languages,” J. ACM 10:4(1963), pp. 487–492.4.J. E. Hopcroft, “An n log n algorithm for minimizing the states in a finite automaton,” inZ. Kohavi (ed.) The Theory of Machines and Computations, Academic Press, New York,pp. 189–196. (Хопкрофт Дж. Алгоритм для минимизации конечного автомата. —Кибернетический сборник, Новая серия, вып. 11. — М.: Мир, 1974. — С. 177–184.)5.D. A. Huffman, “The synthesis of sequential switching circuits,” J. Franklin Inst. 257:3-4(1954), pp. 161–190 and 275–303.6.S.
C. Kleene, “Representation of events in nerve nets and finite automata,” inC. E. Shannon and J. McCarthy, Automata Studies, Princeton Univ. Press, 1956, pp. 3–42.(Клини С.К. Представление событий в нервных сетях. — сб. “Автоматы”. —М.: ИЛ, 1956. — С. 15–67.)7.E. F. Moore, “Gedanken experiments on sequential machines,” in C. E. Shannon andJ. McCarthy, Automata Studies, Princeton Univ. Press, 1956, pp.
129–153. (Мур Э.Ф.Умозрительные эксперименты с последовательностными машинами. — сб. “Автоматы”. — М.: ИЛ, 1956. — С. 179–210.)8.R. E. Stearns and J. Hartmanis, “Regularity-preserving modificationsexpressions,” Information and Control 6:1 (1963), pp. 55–69.9.J. I. Seiferas and R. McNaughton, “Regularity-preserving modifications,” TheoreticalComputer Science 2:2 (1976), pp. 147–154.184Стр. 184ofregularÃËÀÂÀ 4.
ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂÃËÀÂÀ 5Êîíòåêñòíî-ñâîáîäíûåãðàììàòèêèè ÿçûêèПерейдем от рассмотрения регулярных языков к более широкому классу языков, которыеназываются контекстно-свободными. Они имеют естественное рекурсивное описание в виде контекстно-свободных грамматик. Эти грамматики играют главную роль в технологиикомпиляции с начала 1960-х годов; они превратили непростую задачу реализации синтаксических анализаторов, распознающих структуру программы, из неформальной в рутинную, которую можно решить за один вечер.
Позже контекстно-свободные грамматики стали использоваться для описания форматов документов в виде так называемых определенийтипа документов (document-type definition — DTD), которые применяются в языке XML(extensible markup language) для обмена информацией в Internet.В этой главе определяется система записи контекстно-свободных грамматик и показывается, каким образом они определяют языки. Обсуждается понятие дерева разбора,изображающего структуру, которую грамматика налагает на цепочки языка. Дерево разбора представляет собой выход синтаксического анализатора языка программирования иодновременно общепринятый способ выражения структуры программы.Контекстно-свободные языки также описываются с помощью магазинных автоматов,рассматриваемых в главе 6.
Эти автоматы не столь важны, как конечные, однако в качестве средства определения языков они эквивалентны контекстно-свободным грамматикам и особенно полезны при изучении свойств замкнутости и разрешимости контекстносвободных языков (глава 7).5.1. Êîíòåêñòíî-ñâîáîäíûå ãðàììàòèêèНачнем с неформального представления контекстно-свободных грамматик, затемрассмотрим их некоторые важные свойства. Далее определим их формально и представим процесс “вывода”, с помощью которого грамматика задает цепочки языка.5.1.1.
Íåôîðìàëüíûé ïðèìåðРассмотрим язык палиндромов. Палиндром — это цепочка, читаемая одинаково слеванаправо и наоборот, например, otto или madamimadam (“Madam, I'm Adam” — по преданию, первая фраза, услышанная Евой в Райском саду). Другими словами, цепочка wявляется палиндромом тогда и только тогда, когда w = wR. Для упрощения рассмотримСтр. 185описание палиндромов только в алфавите {0, 1}. Этот язык включает цепочки вроде0110, 11011, ε, но не включает 011 или 0101.Нетрудно проверить, что язык Lpal палиндромов из символов 0 и 1 не является регулярным.
Используем для этого лемму о накачке. Если язык Lpal регулярен, то пусть n —соответствующая константа из леммы. Рассмотрим палиндром w = 0n10n. Если Lpal регулярен, то w можно разбить на w = xyz так, что y состоит из одного или нескольких нулейиз их первой группы. Тогда в слове xz, которое также должно быть в Lpal, если Lpal регулярен, слева от единицы будет меньше нулей, чем справа. Следовательно, xz не можетбыть палиндромом, что противоречит предположению о регулярности Lpal.Существует следующее естественное рекурсивное определение того, что цепочка изсимволов 0 и 1 принадлежит языку Lpal. Оно начинается с базиса, утверждающего, чтонесколько очевидных цепочек принадлежат Lpal, а затем использует идею того, что еслицепочка является палиндромом, то она должна начинаться и заканчиваться одним и темже символом.
Кроме того, после удаления первого и последнего символа остаток цепочки также должен быть палиндромом.Базис. ε, 0 и 1 являются палиндромами.Индукция. Если w — палиндром, то 0w0 и 1w1 — также палиндромы. Ни одна цепочка не является палиндромом, если не определяется этими базисом и индукцией.Контекстно-свободная грамматика представляет собой формальную запись подобныхрекурсивных определений языков. Грамматика состоит из одной или нескольких переменных, которые представляют классы цепочек, или языки. В данном примере нужна толькоодна переменная, представляющая множество палиндромов, т.е.
класс цепочек, образующих язык Lpal. Имеются правила построения цепочек каждого класса. При построении используются символы алфавита и уже построенные цепочки из различных классов.Пример 5.1. Правила определения палиндромов, выраженные в виде контекстно-свободной грамматики, представлены на рис. 5.1.
В разделе 5.1.2 мы рассмотрим их подробнее.Первые три правила образуют базис. Они говорят, что класс палиндромов включаетцепочки ε, 0 и 1. Эти правила образуют базис, поскольку ни одна из их правых частей(справа от стрелок) не содержит переменных.Последние два правила образуют индуктивную часть определения. Например, правило 4 гласит, что если взять произвольную цепочку w из класса P, то 0w0 также будет вклассе P. Аналогично, по правилу 5 цепочка 1w1 также будет в классе P. 1.P→ε2.P→03.P→14.P → 0P05.P → 1P1Рис. 5.1.
Контекстно-свободная грамматика для палиндромов186Стр. 186ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈ5.1.2. Îïðåäåëåíèå êîíòåêñòíî-ñâîáîäíûõ ãðàììàòèêОписание языка с помощью грамматики состоит из следующих четырех важныхкомпонентов.1.Есть конечное множество символов, из которых состоят цепочки определяемогоязыка. В примере о палиндромах это было множество {0, 1}. Его символы называются терминальными, или терминалами.2.Существует конечное множество переменных, называемых иногда также нетерминалами, или синтаксическими категориями. Каждая переменная представляет язык,т.е. множество цепочек. В рассмотренном примере была только одна переменная, P,которая использовалась для представления класса палиндромов в алфавите {0, 1}.3.Одна из переменных представляет определяемый язык; она называется стартовымсимволом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
