XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 80
Текст из файла (страница 80)
Затвечание 7.5. Если для какой-то дуги е Е Е ее метка <р(е) есть язык (Л), то, поскольку этот язык не является подмножеством алфавита У, в этом случае у(е) Я У, и, наоборот, 7.5. Ковечвые автоматы. 7еорена Клияя 503 если ср(е) С У, то исключается, что ~р(е) = (Л). Таким образом, два рассмотренных случая для значений функции разметки исключают друг друга, на что и было указано в рассмотренном вьппе неформальном описании конечного автомата. На рис. 7.5 изображен конечный ав- О+1 О+1 томат, для которого алфавит У = (О, Ц. Начальное состояние показано входной От О1 О, стрелкой, заключительное — выходной. Метки дуг обычно пишут беэ фигурных скобок.
Разрешена запись меток дуг н в виде регулярных еыразсениб (см. рис. 7.5). Конечный автомат, таким образом, может быть задан как пятерка: М = (Я, Е, у, до, Р), где Я вЂ” множество состояний автомата; Š— множество дуг; ~р — функция разметки (весовая функция), причем для каждой дуги е Е Е ее метка у(е) = (Л) или у(е) С У, при этом подмножество <р(е) не пусто; ос е ц — начальное состояние; г" С Я вЂ” подмножество заключительных состояний.
Алфавит У называется входным алОтаеитпом аетпомотпа М, а его буквы — входными символами (или входными буттеами) данного аетпоматпа. Замечание 7.6. Конечный автомат определен как ориентированный граф, размеченный над полукольцом регулярных языков, но метка дуги задается не как произвольный регулярный язык, а как язык, состоящий иэ одной пустой цепочки, либо язык, являющийся подмножеством букв входного алфавита. Это ни в коей мере не противоречит основному определению размеченного ориентированного графа, ибо совершенно не обязательно, чтобы область значения функции разметки совпадала с носитпелем полукольца. Чисто формально, конечно, можно обобщить определение конечного автомата и допустить в качестве меток дуг произвольные регулярные языки, но, как 504 7.
КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ можно показать, это обобщение не является принципиальным, и такое определение конечного автомата сводится к данному выше определению (см. задачи в конце этой главы). Немаловажно и то, что приведенное формальное определение конечного автомата и задание меток дуг как регулярных языков специального вида согласуются с интуитивным представлением об автомате как об устройстве, которое „побуквенно" читает входные цепочки, переходя из одного состояния в другое.
Требование, чтобы такое устройство за один такт анализировало („обозревало") любое, сколь угодно сложное регулярное выражение, не отвечает нашей „вычислительной" интуиции, в соответствии с которой за один такт может быть произведена только простая операция, каковой и является „реакция" автомата на обозреваемый одиночный символ или на пустую цепочку. ф Если е = (а, г) — дуга автомата М и ее метка у(е) есть регулярное выражение Л, то в этом случае будем говорить, что в автомате М возможен переход иэ сосгполнил д в соспзолиие г по пустой цепочке, и писать д -~Л г. Дугу с меткой Л будем называть Л-переходом (или «усизой дугой). Если же метка дуги е есть множество, содержащее входной символ а, то будем говорить, что в автомате М возможен переход из состояния а в состояние г по символу а, и писать Ч "+а г ° Для конечного автомата удобно ввести в рассмотрение функцию переходое, определив ее как отображение б: ь) х (У 0 (Л)) -~ 2~~, такое, что 6(д,а) = (г: у — ~~ г), т.е.
значение функции переходов на упорядоченной паре (состояние, входной символ или пустая цепочка) есть множество всех состояний, в которые из данного состояния возможен переход по данному входному символу или пустой цепочке. В частности, это может быть пустое множество. 7.5.
Коаечаые автоматы. Теорема Канам 505 На рис. 7.5 б(до,О) = (до од), б(до,1) = (оо)з б(од>0) = (Яг)в б(В,1) = а~, б(йг,О) = (чг), б(чг 1) = (чг) Понятие функции переходов конечного автомата позволяет дать и математическую интерпретацию системы команд. С этой точки зрения система команд есть просто способ представления конечной функции, а именно функции переходов. Система команд есть конечное множество ноааанд вида оа-+ т, где о и т — состояния автомата; а — входной символ или пустая цепочка, причем указанная команда тогда и только тогда содержится в системе команд, когда д -+„г. Содержательная интерпретация команды была приведена вьппе. Стрелка (-+), как и в записи правила грамматики, есть „метасимвол".
Он не содержится ни в одном ю алфавитов, фигурирующих в определении конечного автомата. Система команд автомата, юображенного на рис. 7.5, приведена ниже: ЧоО -+ Чо йоО-+ дд, чо1 -+ Чо, ддО-~ йг, Ч20 + Чг 621 ~ Яг. Используя функцию переходов, конечный автомат можно задавать как упорядоченную пятерку: бб = ('т', Я, йо, Р, б), где У вЂ” входной алфавит; Я вЂ” множество состояний; дев начальное состояние; Р— множество заключительных состояний; б — функция переходов, заданная в виде системы команд. Как правило, в дальнейшем мы именно так и будем определять конечный автомат. 506 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ Конечный автомат называют номносптью определенным, если из каждого его состояния по каждому входному символу возможен переход в некоторое состояние, т.е. (ЧЧ Е ьт)(та Е Ч) Яд,а) ~ И). Заметим, что в полностью определенном конечном автомате, вообще говоря, могут существовать и переходы по пустой цепочке.
Конечный автомат называется детнерминированнъиц если в нем нет дуг с меткой А и из любого состояния по любому входному символу возможен переход в точности в одно состояние, т.е. (1тд Е чт)(та Е 'т')(~в(д,а)~ = 1). Конечный автомат называется коаэидетперлеинированным, если в нем нет дуг с меткой А и из любого состояния по любому символу возможен переход не более чем в одно состояние, т.е. (Чд Е Я)(Уа Е У)(~б(д,а)~ ~ ~1). Замечание Т.Т. Для детерминированного конечного автомата значением функции переходов для любой пары (состояние, входной символ) является одноэлементное подмножество множества состояний.
Поэтому естественно понимать функцию переходов детерминированного конечного автомата не как отображение множества Я х т' в множество 2н, а как отображение множества ст х 'т' в само множество состояний ьт. Впредь так и будем рассматривать функцию переходов детерминированного конечного автомата, не оговаривая этого особо. ф Согласно общему определению метаки путав в размеченном ориентированном графе, метана аутпи в конечном автомате есть соединение" меток входящих в этот путь дуг (в порядке их прохождения).
Таким образом, метка любого путав конечной длины в конечном автомате есть регулярный язык. Отметим, что Умнолеелвем ооеттюмьил тс(1") лвллетсл сеедлнелие леыкее. 7.о. Ковечвые автоматы. Теорема Клвви 507 мы, юучая размеченные ориентированные графы,предполагаем, что рассматриваются только пути конечной длины. Так, для автомата, изображенного на рис. 7.5, метка пути де, де, ом дз равна соединению языков (О, Ц .
(01 (О) = (000, 1001, что можно записать в виде регулярного выражения (0+ 1)00, а метка пути до, дм дз, сз, оз может быть задана таким регулярным выражением: 00(0+1)(0+1) =00(00+01+10+11) = = 0000+ 0001+ 0010+ 0011, что означает, что эта метка есть множество цепочек (0000, 0001, 0010, 001Ц. Метку пути тт' конечной длины обозначим через ~р'(тт'). Здесь ~р' — это функция, отображающая множество всех путей конечной длины в размеченном ориентированном графе, в полукольцо К(У). Для пути тт' длины 1 значение ~р'(Ю) = у(Ж), т.е. функция разметки ориентированного графа есть ограничение функции ~р' на множество всех путей длины 1. Если цепочка х принадлежит метке некоторого пути И~— пути, ведущего ю вершины д в вершину г конечного автомата М, то говорят, что цепочка х читаетсл на пути тт' в М или что путь И~ несет цепочку х. Пишем о =ь' т, если х читается на некотором пути из о в г.
В том случае, когда явно надо указать давку и пути, на котором читается цепочка х, записываем о =оов т. Если нужно подчеркнуть, что цепочка х читается на некотором пути ненулевой длины из о в т, то используем запись д =э+ т. В терминах неформального описания конечного автомата любому пути, на котором читаетсл входная цепочка х, отвечает последовательность конфигураций, которую проходит автомат, читая посимвольно входную цепочку, записанную на ленте, и продвигая головку на один символ вправо за один такт.
508 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ Супоимостиь прохождения ю состояния е в состояние г есть (согласно общему определению этого понятия в размеченных ориентированных графах) объединение меток всех путей', ведущих ю д в т, т.е. множество всех таких х, что д ~л т. Это значит, что элемент се; мапзрацм сплоимостией есть язык Говоря об элементе се, матрицы стоимостей, мы отождествляем обозначение состояния автомата с его номером в некоторой нумерации состояний как вершин ориентированного графа. В частности, лэым ЦМ) монечного пегпомаплп М есть множество всех цепочек во входном алфавите, читаемых в М на некотором пути ю начального состояния в одно из заключительных состояний. Другими словами, ЦМ) =(х: Чо=а;~УУ ЧУЕР1= Ц столу Рб) Оугр где г' — множество заключительных состояний.
Таким обрезом, язык конечного автомата есть объединение тех элементов матрицы стоимостей автомата, которые находятся в строке, соответствующей начальному состоянию до, и в столбцах, соответствующих всем заключительным состояниям яу б Р. Замечание 7.8. Необходимо обратить внимание на одну очень важную вещь. В конечном автомате метка произвольного пути конечной длины есть регулярный язык, поскольку он вычисляется как соединение конечного семейства регулярных языков.
Но стоимость прохождения между заданной парой вершин априори не является регулярным языко, так как множество путей, ведущих из одной вершины в другую, может "Здесь объединение поннмаетсл как бесконечкел сумме замкнутого полукольна С(Ъ') всех языков в алфавите У, т.е. как тпочнал еерзиал ерове последовательности языков относительно теоретико-мкоиествениого вкыоченил. 7.о„Ковечвые автоматы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
