Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 47
Текст из файла (страница 47)
Для любого алгоритма, понимаемого в интуигпивном смысле, можно постпроить машину Тьюринга, функционирование которой эквивалентно этому алгоритму. Синтезируем машину Тьюринга, реализующую прибавление 1 к целому и-разрядному числу, представленному в троичной системе с алфавитом цифр 10, 1, 21 (рис. 4.3, а). Алгоритм реализации этой операции представлен на рис. 4.3, б, где символ в квадратных скобках обозначает содержимое наблюдаемого УГ разряда, Введя нетерминальные символы Ям Ят, Яз, нетрудно определить соответствующую машину Тьюринга (рис.
4.3, в), где то = О, 1, 2; Л вЂ” левое движение на 1 разряд, П вЂ” правое движение на 1 разряд, Н вЂ” движение УГ отсутствует. Понятие машины Тьюринга является строгим уточнением понятия алгоритма. Переход от интуитивного понятия алгоритма Рве. 4.З к точному понятию машины Тьюринга позволяет решить вопрос алгоритмической (машинной) разрешимости той или иной проблемы. Один из первых отрицательных результатов был получен американским ученым Черчем в 1936 г.
при рассмотрении проблемы 263 262 Гл.4. Теория фо яалъных грамматик и овтпомотов $4.1. Формальные грамматики распознавания выводимости в математической логике: определить для любых заданных формул В и Я в логическом исчислении, существует дедуктивная цепочка, ведущая от В к 5, или нет. Если формула А может быть преобразована в формулу В однократным применением допустимой подстановки, и наоборот, то А и  — смежные формулы. Последовательность А;, т = 1, 2, ..., п, формул, соседние из которых смежны, называется дедуктивной цепочкой, ведущей от Ат к А„. Под решением проблемы распознавания выводимости понимается алгоритм, дающий ответ на вопрос о существовании дедуктивной цепочки (для любых Я и Я). Проблема является алгоритмически неразреши.ной, если не существует алгоритма (соответствующей машины Тьюринга) для ее решения.
Отдельная машина Тьюринга может быть представлена как программа произвольного вида для ЦВМ с потенциально бесконечной памятью. Теорема 4.1 (Черч). Проблема распознавания выводимостпи алгоритмически неразрешима. Следуя Хамскому, введем ограничения на подстановки ст -ь ~3, прослеживая при эхом соответствие полученной грамматики автоматическому устройству. Ограничение 1. Если ст -+ 3 удовлетворяет выражению (4.1), т. е. является правилом вывода, то (Ват, агз ° .е а„„Ьт, Ьг) ., Ь»(т ~ и)) ((ст = = агаг...а,„) бс (13 = Ьгбг...
Ь»)). (4.2) Язык, порожденный грамматикой, удовлетворяющей (4.2), реализуется машиной Тьюринга. Ограничение 2. Если ет-+Р— правило вывода, то (В7м 7г а1 ит(7м 7г, ш — цепочки, а — отдельный символ; ит не пусто)) ((ст = 7га7г) ее (т3 = 'угш7г)) (4 3) Грамматики, удовлетворяющие соотношению (4.3), называются контекстными (контекстпно связанными). Контекстные грамматики реализуются устройствами типа автомата Майхилла. Пусть (т, у, /с, 1, р) — одно из правил, определяющих работу автомата: если блок управления находится в состоянии Ят, а считывающая головка — напротив клетки, содержащей символ тщ, то блок управления может перейти в состояние Яь, в то время как лента продвигается в ! клеток влево, а рассматриваемый символ заменяется на тпр.
Устройство, работающее по такому принципу, называется автпоматом Майхилла. Ограничение 3. Если сг -+ Д вЂ” правило вывода, то сев нетерминальная буква и (4.4) (4.5) (4.6) праволинейным, если А-+ хВ; леволинейным, если А-+ Вх. (4.7) Правило вида А -+ х называется заключительным.
В зависимости от ограничений, определяемых правилами (4.5)-(4.7), бесконтекстная грамматика может быть: а) линейной, если каждое ее незаключительное правило линейно (в частности, оно леволинейно или праволинейно); 6) односторонне линейной, если каждое ее незаключительное правило леволинейно или каждое ее незаключительное правило праволинейно; в) металинейной, если все ее незаключительные правила либо линейны, либо имеют вид Я -ь Д и если, кроме того, в ней нет правил вида А -ь стЯ13 ни для каких А, ет, ту, где сг, ф не лусты. Грамматика, удовлетворяющая (4.4), называется бесконтпекстпной (контекстно свободной).
Согласно (4.4) каждое правило грамматики утверждает, что определенный нетерминальный символ может быть заменен цепочкой символов независимо от контекста. Язык, порождаемый бесконтактной грамматикой, реализуется автоматом Майхилла специального вида, в котором используется магазинная память. Этот автомат, следуя Ньюэллу, Шоу и Саймону, будем называть магазинным аетоматом. Магазинный автомат представляет собой композицию управляющего автомата н трех магазинов, каждый из которых представляет собой бесконечную в одну сторону ленту.
На ленте записано слово, первая буква которого записана в первой ячейке, вторая — во второй и т. д. При чтении воспринимается первая буква слова, затем она стирается и оставшаяся часть слова сдвигается к первой ячейке. При записи в магазин слова длины й первые Ь ячеек освобождаются в результате записанного ранее сдвига слава на Ь ячеек. Входной магазин связан с входными каналами управляющего автомата, выходной — с выходными каналами, внутренний магазин связан как с входными, так и выходными каналами управляющего автомата. Множество внутренних состояний управляющего автомата разбито на два подмножества, А и В. Если управляющий автомат находится в состоянии, принадлежащем подмножеству А, то происходит считывание информации из входного и внутреннего магазинов.
Если автомат находится в состоянии Я; б В, то происходит считывание только из внутреннего магазина, при этом автомат переходит в следующее состояние и записывает во внутренний и выходной магазины слова. Правило бесконтекстной грамматики называется: линейным, если оно имеет вид А-ь хВу; 264 Гл. 4. Теория формальных грамматик и автоматов Односторонняя линейная грамматика реализуется конечным авшомао«ом, и порождаемый ею язык называется нонечноавтоматным.
Рассмотрим одностороннюю линейную грамматику, все правила которой праволинейные (для определенности) либо заключительные. Без потери общности можно предположить, что каждое линейное правило имеет вид А -+ аВ, где  — неначальный символ, и что каждое заключительное правило грамматики имеет вид А -«а. Пусть А1, Аз, ..., А„— нетерминальные символы грамматики, причем А1 — начальный символ, Сопоставим грамматике конечный автомат, каждое внутреннее состояние которого взаимно однозначно соответствует нетерминальному символу грамматики, а входной символ — терминальному символу грамматики. При этом если А; -+ аА — правило грамматики, то тройка (а, А;, А ) определяет функционирование автомата и понимается как переход от состояния А; в состояние А при считывании входного символа а.
Для определенности будем считать, что при переходе из состояния Б; в состояние Я в результате входного воздействия а автомат вырабатывает на своем выходе символ 6. Тогда автомат можно определить как четверку (а, 6, Я;, Я ). Если фиксируется начальное сосгаолние Бо, то автомат реализует оператор Т: который в дальнейшем будем называть автоматным. Автоматный оператор Т переводит входную последовательность символов (а;) и выходную (6;) в зависимости от начального состояния и реализуемой односторонней линейной грамматики.
Автомат удобно представлять в виде функции Т на графе 0 = (У, Ц, каждой вершине которого взаимно однозначно соответствует состояние автомата, и если из состояния Б; в состояние Я автомат переходит в результате входного воздействия а, вырабатывая при этом выходной символ 6, то соответствующие вершины ьй и о соединены дугой (о;, о ), взвешенной парой (а, 6). Таким образом, областью определения этой функции Т является граф С = (У, е«'), построенный рассмотренным выше способом, а областью значений — входные, выходные символы и идентификаторы состояний автомата. Рассмотрим, например, одностороннюю линейную грамматику с алфавитом терминальных символов Мт = 4х, у, а, 6), с алфавитом нетерминальных символов МЬ1 = (Б1, Яз, Яз3 и следующими правилами вывода: Я1 -+ уЬЯ1, Я1 -+ хаБэ Ят -+ хаЯз, Яз -+ уаЯз, Яз -+ х6Б1.
Эта грамматика реализуется конечным автоматом. Если автомат установить в начальное состояние Я1 и подать на вход после- З4.2. Основные этапы проектирования автоматов 265 довательность терминальных символов (у, х, у, ху, то на выходе получаем последовательность терминальных символов (Ь, а, а, 6), нетерминальные же символы образуют последа- (х, в) вательность (Я1, Ям Бъ Бз). Реализуемый автоматный оператор Т можно представить в виде соответствующей функции на графе С = (У, Щ ~™' (рис. 4.4). Если рассматривать автомат не как устройство, реализующее соответствующую граммати- 1кю ку, а изучать его строение (структуру), то следует Рнс.
4.4 представлять этот автомат не в виде машины Тьюринга, а в виде блок-схемы, изображенной на рис. 4.5, где Мв — множество вход- м+-4хА 2 (хю] ме 1 Рис. 4.5 ных терминальных символов, Му — множество выходных терминальных символов, М, — множество нетерминальных символов (М,=М+,М, ). $4.2.
Основные этапы проектирования автоматов Рассмотрим проблему проектирования автомата. На рис. 4.5: М вЂ” множество входных векторов Х = хв'х" ...х'" 1 2 и 1 ̄— множество выходных векторов у ве аг в,н. М, — множество векторов, характеризующих входные каналы обратной связи (памяти), г-=(;) (,;)"...(х;)"; М,+ — множество векторов, характеризующих выходные каналы обратной связи, Я+ = (х+)" (х+)"' ..(х+) '. Каждый из каналов в случае й-значной логики может находиться в одном из уе значений а б 40, 1, „6 — 1«.
Рнс. 4.6 266 Гл.4. Теория формольямх громкотик и оатомотоа Условимся обозначать переменную ст, равную а Е (6, 1, 2, ... ...,А — 11, как сг . Тогда правила вывода в случае автоматной грамматики удобней определить как подстановку ХУ+ -ь У У, в которой начальное значение вектора Я+ и последующие его значения получаются приравниванием значению вектора Я, вычисленному на предыдущем шаге, т. е.
где г — некоторая постоянная времени автомата. Векторы ХЯ+ и Л' У получаются приписыванием справа вектора У+ к Х и У к Я соответственно. Состояния каналов обратной связи в дальнейшем будем называть вкутрекними состодкидми автомата, а постоянную времени г — временем перехода из одного внутреннего состояния в другое, причем в зависимости от назначения автомата и его реализации г может быть постоянной для данного автомата или же зависеть от изменения вектора Х. В первом случае автомат называют синхронным, во втором — асикхрокнььм. При заданном (У+)о последовательность входных векторов Х (входная последовательносг»ь) однозначно определяет последовательность выходных векторов У (выходную последовательность).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
