dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 15
Текст из файла (страница 15)
Если существует несколько входных символов, переводящих автомат из состояния q в состояние p, то диаграмма переходов можетсодержать одну дугу, отмеченную списком этих символов;в) диаграмма содержит стрелку в начальное состояние, отмеченную как Начало. Эта стрелка не выходит ни из какого состояния;г) вершины, соответствующие допускающим состояниям (состояниям из F),отмечаются двойным кружком. Состояния, не принадлежащие F, изображаются простым (одинарным) кружком.64Стр. 64ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛПример 2.2. На рис. 2.4 изображена диаграмма переходов для ДКА, построенного впримере 2.1.
На диаграмме видны три вершины, соответствующие трем состояниям,стрелка Начало, ведущая в начальное состояние q0, и одно допускающее состояние q1,отмеченное двойным кружком. Из каждого состояния выходят две дуги: одна отмечена0, вторая — 1 (для состояния q1 дуги объединены в одну). Каждая дуга соответствует одному из фактов для δ, построенных в примере 2.1. НачалоРис. 2.4. Диаграмма переходов для ДКА, допускающего все цепочки, которыесодержат подцепочку 01Òàáëèöû ïåðåõîäîâТаблица переходов представляет собой обычное табличное представление функции,подобной δ, которая двум аргументам ставит в соответствие одно значение. Строки таблицы соответствуют состояниям, а столбцы — входным символам.
На пересечении строки, соответствующей состоянию q, и столбца, соответствующего входному символу a,находится состояние δ (q, a).Пример 2.3. На рис. 2.5 представлена таблица переходов, соответствующая функции δиз примера 2.1. Кроме того, здесь показаны и другие особенности таблицы переходов. Начальное состояние отмечено стрелкой, а допускающее — звездочкой. Поскольку прописные символы строк и столбцов задают множества состояний и символов, у нас есть вся информация, необходимая для однозначного описания данного конечного автомата.
01→q0q2q0*q1q1q1q2q2q1Рис. 2.5. Таблица переходов для ДКА из примера 2.12.2.4. Ðàñøèðåíèå ôóíêöèè ïåðåõîäîâ íà öåïî÷êèРанее было нестрого обосновано утверждение о том, что всякий ДКА определяетнекоторый язык, а именно: множество всех цепочек, приводящих автомат из начального состояния в одно из допускающих. В терминах диаграмм переходов язык ДКА —это множество меток вдоль всех путей, ведущих из начального состояния в любое допускающее.2.2. ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅ ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛСтр. 6565Теперь дадим строгое определение языка ДКА. С этой целью определим расширенную функцию переходов, которая описывает ситуацию, при которой мы, начиная с произвольного состояния, отслеживаем произвольную последовательность входных символов.
Если δ — наша функция переходов, то расширенную функцию, построенную по δ,∧обозначим δ . Расширенная функция переходов ставит в соответствие состоянию q ицепочке w состояние p, в которое автомат попадает из состояния q, обработав входную∧последовательность w. Определим δ индукцией по длине входной цепочки следующим образом.∧Базис. δ (q, ε) = q, т.е., находясь в состоянии q и не читая вход, мы остаемся в состоянии q.Индукция. Пусть w — цепочка вида xa, т.е. a — последний символ в цепочке, а x —цепочка, состоящая из всех символов цепочки w, за исключением последнего.3 Например, w = 1101 разбивается на x = 110 и a = 1. Тогда∧∧δ (q, w) = δ ( δ (q, x), a)(2.1)Выражение (2.1) может показаться довольно громоздким, но его идея проста.
Для то∧∧го чтобы найти δ (q, w), мы вначале находим δ (q, x) — состояние, в которое автоматпопадает, обработав все символы цепочки w, кроме последнего. Предположим, что это∧∧состояние p, т.е. δ (q, x) = p. Тогда δ (q, w) — это состояние, в которое автомат перехо∧дит из p при чтении a — последнего символа w. Таким образом, δ (q, w) = δ (p, a).Пример 2.4. Построим ДКА, допустимым для которого является языкL = {w | w содержит четное число 0 и четное число 1}.Вполне естественно, что состояния данного ДКА используются для подсчета числанулей и единиц. При этом подсчет ведется по модулю 2, т.е.
состояния “запоминают”,четное или нечетное число 0 или 1 было прочитано на данный момент. Итак, существуютчетыре состояния, которые можно описать следующим образом.q0 : Прочитано четное число 0 и четное число 1.q1 : Прочитано четное число 0 и нечетное число 1.q2 : Прочитано четное число 1 и нечетное число 0.q3 : Прочитано нечетное число 0 и нечетное число 1.Состояние q0 одновременно является и начальным, и единственным допускающим.Начальным оно является потому, что до того, как будут прочитаны какие-либо входныеданные, количество прочитанных и 0, и 1 равно нулю, а нуль — число четное. Это же со3Напомним, что мы условились обозначать символы буквами из начальной части алфавита, ацепочки — буквами из конца алфавита.
Это соглашение необходимо для того, чтобы понятьсмысл выражения “цепочка вида xa”.66Стр. 66ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛстояние — единственное допускающее, поскольку в точности описывает условие принадлежности последовательности из 0 и 1 языку L.Теперь мы знаем почти все, что нужно для определения ДКА, соответствующего языку L.
Это автоматA = ({q0, q1, q2, q3}, {0, 1}, δ, q0, {q0}),где функция переходов δ изображается диаграммой переходов на рис. 2.6. Заметим,что по каждому символу 0 совершается переход через горизонтальную пунктирнуюлинию. Таким образом, после чтения четного числа символов 0 мы находимся над горизонтальной линией, в состоянии q0 или q1, а после нечетного числа — под ней, в состоянии q2 или q3. Аналогично, символ 1 заставляет нас пересечь вертикальную пунктирную линию. Следовательно, после чтения четного числа единиц мы находимся слева от вертикальной линии, в состоянии q0 или q2, а после чтения нечетного — справа, всостоянии q1 или q3. Эти наблюдения представляют собой нестрогое доказательствотого, что данные четыре состояния интерпретируются правильно. Хотя можно и формально, как в примере 1.23, доказать корректность наших утверждений о состояниях,используя совместную индукцию.НачалоРис.
2.6. Диаграмма переходов для ДКА из примера 2.4Данный ДКА можно также представить таблицей переходов, изображенной нарис. 2.7. Но нам нужно не просто построить ДКА. Мы хотим с его помощью показать,∧как строится функция δ по функции переходов δ. Допустим, на вход подается цепочка110101. Она содержит четное число 0 и 1, поэтому принадлежит данному языку. Таким∧образом, мы ожидаем, что δ (q0, 110101) = q0, так как q0 — единственное допускающеесостояние. Проверим это утверждение.∧Для проверки требуется найти δ (q 0, w) для всех постепенно нарастающих, начиная с ε , префиксов w цепочки 110101. Результат этих вычислений выглядит следующим образом.2.2. ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅ ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛСтр. 676701*→q0q2q1*q1q3q0q2q0q3q3q1q2Рис.
2.7. Таблица переходов для ДКА из примера 2.4∧•δ (q0, ε) = q0.•δ (q0, 1) = δ ( δ (q0, ε), 1) = δ (q0, 1) = q1.•δ (q0, 11) = δ ( δ (q0, 1), 1) = δ (q1, 1) = q0.•δ (q0, 110) = δ ( δ (q0, 11), 0) = δ (q0, 0) = q2.•δ (q0, 1101) = δ ( δ (q0, 110), 1) = δ (q2, 1) = q3.•δ (q0, 11010) = δ ( δ (q0, 1101), 0) = δ (q3, 0) = q1.•∧∧∧∧∧∧∧∧∧∧∧∧δ (q0, 110101) = δ ( δ (q0, 11010), 1) = δ (q1, 1) = q0.Ñòàíäàðòíûå îáîçíà÷åíèÿ è ëîêàëüíûå ïåðåìåííûåПо прочтении этого раздела может сложиться впечатление, что нужно обязательнопользоваться введенными здесь обозначениями, т.е. функцию переходов обозначатьδ, ДКА — буквой A и т.д.
Действительно, во всех примерах мы стараемся использовать одинаковые переменные для обозначения однотипных объектов. Делается этодля того, чтобы легче было вспомнить, о каком типе переменных идет речь. Так, впрограммах i почти всегда обозначает переменную целого типа. Однако в выбореобозначений для компонентов автомата (или чего-либо другого) мы совершенно свободны. Например, при желании мы можем обозначить ДКА буквой M, а его функциюпереходов — буквой T.Более того, нет ничего странного в том, что одна и та же переменная обозначает, взависимости от контекста, разные объекты. Например, функции переходов в примерах 2.1 и 2.4 обозначены буквой δ. Но эти две функции являются локальными переменными и относятся только к своим примерам.
Они значительно отличаются друг отдруга и никак не связаны.2.2.5. ßçûê ÄÊÀТеперь можно определить язык ДКА вида A = (Q, Σ, δ, q0, F). Этот язык обозначаетсяL(A) и определяется как68Стр. 68ÃËÀÂÀ 2. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ∧L(A) = { w | δ (q0, w) принадлежит F}.Таким образом, язык — множество цепочек, приводящих автомат из состояния q0 водно из допускающих состояний. Если язык L есть L(A) для некоторого ДКА A, то говорят, что L является регулярным языком.Пример 2.5. Ранее упоминалось, что если A — ДКА из примера 2.1, то L(A) — множество цепочек из 0 и 1, содержащих подцепочку 01. Если же A — ДКА из примера 2.4, тоL(A) — множество всех цепочек из 0 и 1, содержащих четное число 0 и четное число 1. 2.2.6. Óïðàæíåíèÿ ê ðàçäåëó 2.22.2.1.На рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
