XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 90
Текст из файла (страница 90)
ф Основной результат, рассматриваемый в этом дополнении, составляет следующая теорема. Теорема 7.13. Если Ь С т'" и К С тт' — регулярные юыки, о С 1г' х тт' — конечная подстановка, то гт(Ь) и о 1(К)— регулярные языки в алфавитах тт' и т' соответственно. 568 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ ~ Регулярность языка сг(с.) легко доказывается индукцией по построению регулярного выражения с привлечением теоремы 7.12, и детали этого доказательства нетрудно восстановить. Доказательство регулярности языка о д(К) значительно труднее. Мы используем „технику буферов", которая оказывается полезной в теории формальных языков при доказательстве многих утверждений. Пусть М = (9, 'гг', до, Р, о) — конечный автомат, допускающий язык К.
Построим конечный автомат М' = Я', 1г, во Р', У) следующим образом. 1. С~« = (во) 0 ([д,х]: д Е Я, х Е гг'(") = гг'~ 0 гг'~ дд... 0 гг "), где Й= днах ]у[, во ФЮ. уеа«ад а ей' С интуитивной точки зрения множество Я«состояний конечного автомата М' включает „новое" состояние во и конечное множество упорядоченных пар из «„С х ИГДвД, где л — наибольшая длина среди всех длин слов иэ образов букв алфавита 1г по подстановке «г. Образно говоря, каждое состояние нового автомата определяется состоянием старого автомата (допускающего К) и содержимым „буфера" конечной длины «с для слов иэ гу', длина которых не превышает Й.
2. Р'=([ду,Л]«ду Е Р). 3. Система команд 6' содержит команды следующих видов: (с) воа -+ [до, х], где а Е дг 0 (Л), х Е сг(а); (сс) [д,ах] ~ [р,х] в том и только в том случае, когда 6 содержит команду да -+ р, а Е гг, х Е дд«««; (с«с) [д, Л]а -+ [д, х], где х Е сг(а), а Е У, д Е (~. Неформально работа конечного автомата М' может быть описана следующим образом.
Если входная цепочка у = Л, то М' допускает цепочку ЛЕ«г д(Л). Это соответствует команде вида (с) при а = Л (при условии, конечно, что до Е Р, т.е. что Л Е К). Если у ~ Л, то М' прочитает символ у(1) и по команде вида (с) „заполнит буфер" какой-то цепочкой из множества сг(у(1)), т.е. перейдет в одно иэ состояний [до,хд], где хд Е сг(у(1)). Далее М' начинает „моделировать" работу конечного автомата М 569 Д.7.4. Мшввям 2ьюрввгв (согласно командам вида (Й)), „читая содержимое буфера" и не обращая внимания на вход, т.е.
делая Л-такты. Исчерпав цепочку хм М' перейдет в состояние [гм Л], где дв =. '' г1 в М. и Если у = у(1) и г1 й Р, то н(у) П К ф ю и у Е сг 1(К). Иначе автомат может допустить другую цепочку из о(у(1)) и т.д. В том случае, если ни из одного состояния [дв, х1] нельзя попасть в состояние [97, Л], ду й Р, однобуквеннэл цепочка у ф о 1(К) и М' „зависает" в незаключительном состоянии. Если цепочка у имеет второй символ у(2), то по команде вида (ссс) будет обеспечена „подкачка буфера" некоторой цепочкой хг Е н(у(2)) и М' опять начнет работать за конечный автомат М, читая буфер, и т.д. Нетрудно видеть, что [де)х1] ~ [гмЛ] ~ [гмхэ] ~ (тэ,Л] =ь ...
=. '' [1;„,Л], гш й Р при хс Е сг(у(с)) для всех с = 1,...,т и ]у] = т тогда и только тогда, когда цепочка х1хэ... хш читается на некотором пути из дв в гш, т.е. когда н(у) П К ~ ю и у е сг 1(К). Строгое доказательство равенства ЦМ') = ~т ~(К) основано на индукции по длине пути в графе автомата. Это доказательство мы не приводим.
~ Следствие Т.б. Если Ь С У' и К С ФУ' — регулярные языки, Ь: У' -+ Ж' — морфиэм, то ЦЬ) и й 1(К) — регулярные языки в алфавитах И7 и У соответственно. Ф С интуитивной точки зрения доказанные результаты означают „устойчивость" множества регулярных языков относительно преобразований, задаваемых конечными подстановками (в частности, морфвзмами). Дополнение 7.4.
Машины 'Хьюринга В этом дополнении мы рассмотрим автомат, называемый автоматом Тьюринга, или машиной Тьюринга, который является анализирующей моделью для языков типа О. Одновременно 570 т. кОнечные АВтОмАты и РеГУлЯРные Языки машина Тьюринга является одним иэ математических опреде- лений алгоритма. Определение 7.12. Машина Тьюринеа определяется кортежем вида Т = (Ч, У, *, а, Я, Ь, В, йо, Яу, б), где Я вЂ” конечное множестпво состпо*ний; У вЂ” конечный входной алд)авипз; * ф У вЂ” символ, называемый маркером начала лентпы; О ф У вЂ” символ, называемый пистпым (или пробелом); о, Ь, В ф У вЂ” символы, называемые символами направленил движения золовки; йо е ц — начальное состояние; ду Е Я вЂ” заключительное состояние; б — ф)тнкиил переходов, являющаяся отображением вида х (У ц (я с))) т 2(0~~(1' О(* п))х)явь н)) причем значение б(й, а), коль скоро оно определено, есть конечное (возможно, и пустое) множество упорядоченных троек из соответствующего декартова произведения.
Функция переходов может быть записана в виде систпемы команд. Каждая команда есть слово вида йа-+гЬ,М, где а, Ь Е У 0 (е, Р), М Е (о', т, В), -+ ф У 0 (*, П, о', т', В). Слово йа (до стрелки) называется левой частною команды, а слово гЬ,М (после стрелки) — правой частпью команды. Неформально работу машины Тьюринга можно представить следующим образом.
Машина имеет истпройстпво )тправленил, которое может находиться в одном из состояний множества Я, полубесконечную ленту, разделенную на ячейки, в каждой из которой может быть записан символ из алфавита У 0 (я, П), причем крайняя левая ячейка хранит символ *, и головку чтения-записи, которая в каждый момент дискретного 571 Д.7.4. Мапппгы 7Ьюрввга времени обозревает квкую-то одну ячейку ленты. Символ П (пробел) не следует путать с пустой цепочкой — это специальный символ, означающий пустую, т.е.
не храншцую символов алфавита У 0 (*), ячейку ленты. Команда, записанная вьппе, разрешает машине Тьюринга, устройство управления которой находится в состоянии д, а головка обозревает ячейку, храняшую символ а, перевести устройство управления в состояние г, записав в обоэреваемую ячейку символ Ь (который может и совпадать с а), и оставить головку на прежнем месте, если М = Я, сдвинуть ее на одну ячейку влево, если М = 4, или на одну ячейку вправо, если М = В. Таким образом, в отличие от конечных явшомяшов машина Тьюринга может модифицировать содержимое ленты (т.е.
является преобразователем), а также передвигать головку в любом направлении. Впредь условимся говорить о состоянии машины Тьюринга, подразумевая состояние ее устройства управления, и об обоэреваемом символе, подразумевая под этим символ той ячейки ленты, которая обозревается в данный момент головкой. Формально поведение машины Тьюринга описывается в терминах конфигураций. Оцределеиие 7.13. Хонфегррацил мап4нны Тьюринга Т есть кортеж (д, х, р) Е Я х (УО(*, П))' х (У 0(*, П)) .
Из конфигурации С = (д, х, ау) непосредственно выводится конфигурация С'= (г, х, Ьу), если да-+ гЬ, Я Е б. Из конфигурации С = (д, хс, ау) непосредственно выводится конфигурация С' = (г, х, сЬу), если да -+ гЬ, Ь е 6. Иэ конфигурации С = (д, х, осу) непосредственно выводится конфигурация С' = (г, хЬ, су), если са-> гЬ, В Е б. Выводом на множестве конфигураций машины Тьюринга называется произвольная последовательность конфигураций 572 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ Св, См ..., С„, ..., такая, что (~6 > 0)(С, 1- С;+и если С;+1 существует).
Конфигурация С' выводима из конфигурации С, если существует вывод С = Св ~- ... )- С„= С'. Число и называется при этом длиной вывода. Все обозначения, касающиеся выводимости на множестве конфигураций машин Тьюринга, остаются такими же, как в случае конечных и магазинных автоматов. Конфигурация есть тройка (состояние, часть цепочки на ленте до головки, часть цепочки на ленте, первый символ которой обозревается головкой). При этом, по соглашению, любая цепочка из множества хП' (для фиксированного х е Е (У 0 (*, П))') отождествляется с цепочкой х, т.е. можно отбрасывать любое число пробеюв в конце слова.
Определение 7.14. Машина Тьюринга называется депзерминированной, если из каждой конфигурации этой машины непосредственно выводится не более чем одна конфигурация. Нетрудно видеть, что машина Тьюринга является детерминированной тогда и только тогда, когда в ее системе команд не существует двух разных команд с одной и той же левой частью. Далее будем рассматривать только детерминированные машины Тьюринга, называя их просто машинами Тьюринга.
Онределенне 7.15. Словарная (вербальная) функция в алфавите У есть произвольное частичное отображение множества слов в алфавите 1' в себя. Определение 7.16. Будем говорить, что машина Тьюринга Т применима к слову р е У', если из конфигурации (дв, А, яр) выводится конфигурация (уу, А, *я) для некоторого э Е У'. Слово я будем называть в этом случае реэулыпапзом применения машины Тьюринга Т к слову р и обозначать его Т(р). Факт применимости машины Т к слову р будем обозначать '.Т(р); если же Т не применима к р, то будем записывать -!Т(р).
Д.7.4. ЛХашивы ЪЪюрввго 573 Множество всех слов р, таких, что .'Т(р), называется обласгпаю применимостпи машины Тьюринеа Т. Определение 7.17. Словарная функция од в алфавите У называетсл еычислимоб но Тьюринер, если существует такая машина Тьюринга Т„, с входным алфавитом У', содержащим К, что х Е Р(р) <=о '.Т, (х) Л (Т„,(х) = од(х)). Пример 7.15. Рассмотрим натуральное число н как слово О!" в алфавите (О, !), а сложение двух натуральных чисел зададим как словарную функцию АРР в алфавите (О, !,1), преобразующую слово О!" 10!'в в слово О!"+'в. Тогда функция АРР вычислима но Тьюрингу, поскольку приведенная ниже система команд определяет машину Тьюринга для сложения двух натуральных чисел: Тлдддг = ((до,дд,дг,дв дв дв,дв,дт,Я,(0,!1) * и 8,1,В до,дв,б), где система команд д имеет следующий вид: до* -+ до'ь> В (1) доО -+ доО В (2) до! -+ до!,В, (3) до1 -+ дд!,В, (4) ддО ~ дд!,В, (5) дд! -~ дг! В (6) дг! ~ дг!, В, (7) дгП -+ двСд>1~ (3) дв! ~ двпэ~) (О) д4! — д д П,ь, (10) дв! -+ дв!>5) (11) двО-+ двО Ь (12) дв*-+ дв*,Я, (13) ддсд -> двс1>Ь, (14) д,! -+ „п,ъ, (15) дг! ~двп,Ь (16) 574 У.
КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ Определенная таким образом машина Тьюринга, получая „на вход" слово 0~" 10~п', где п,пв > О, оставаясь в состоянии дв, „бежит" вдоль ленты слева направо до тех пор, пока не встретит символ 1 (играющий роль „разделителя" двух слагаемых). „Увидев" этот символ, машина перейдет в состояние щ, заменив символ 1 „палочкой" (~). Следующий затем символ 0 (первый символ второго слагаемого) заменяется „палочкой". Таким образом, после „пробега" второго слагаемого в результирующем слове будет на две „палочки" больше, чем следует. Если второе слагаемое не равно О, то после выполнения команды (5) будет применима команда (6), а поспе нее — команда (7).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
