Занятие Содержание занятия «Модели конечных автоматов»

Конечные автоматы.

Рассмотрим систему подстановок, задаваемую алфавитом М ={m_i / i= 1, ..., р} и базисными подстановками

_i_i, (1.1)

где _i, _i; - формулы (слова), быть может, пустые в алфавите М.

Каждую подстановку _ii будем понимать как правило вывода. Часто систему подстановок называют полусистемами Туэ, в честь норвежского математика Акселя Туэ. Используя эти полусистемы, Хомский сформировал и развил аппарат формальных грамматик.

Определим понятие формальной грамматики, которую в дальнейшем будем называть просто грамматикой. Рассмотрим конечный алфавит М = {т₁, т₂, .., т_n}, элементы которого будем называть символами (буквами), а конечные последовательности символов — словами.

Обозначим все множество слов, на длину которых не наложены никакие ограничения, Я₀. Будем говорить, что Я  Я₀ - язык в алфавите М.

Пусть G - некоторая совокупность правил, с помощью которых в М порождаются все слова, принадлежащие языку Я, и только они. Совокупность правил О будем называть грамматикой языка Я.

Два языка будем называть эквивалентными, если множества слов, из которых они состоят, совпадают. Две грамматики G₁ и G₂ над Я называются эквивалентными, если языки, ими порождаемые, эквивалентны.

Условимся говорить, что G - грамматика с конечным числом состояний, если правила порождения слов из алфавита М= [т₁, т₂, ..., m_n} задаются следующим образом. Существует конечное множество состояний {S₀, S₁,..., S_r} и каждому S_j, (j=1,2,... ,r) сопоставляется набор пар вида (m_i,S_q), где i = {1, 2,..., п}, q = {0, 1,..., r}. Состоянию S₀ сопоставляются пары вида (т₀,,S_h ), где h {1, 2, ..., r}. Символ m₀ - специальный знак пробела между словами. Конструирование слов происходит следующим образом: из состояния S₀ совершают переход в любое состояние S_q, из тех S_q, которые являются вторыми членами пар вида (m₀,S_q), и в начале слова ставят знак пробела. Исходя из пар, сопоставленных выбранному S_q, берут любую (m_i,S₁). Этот выбор определяет следующее состояние S₁ и первый символ слова m_i. Далее процесс построения слова происходит аналогично. Слово заканчивается при переходе к заключительному состоянию, как правило S₀. Язык, порождаемый грамматикой с конечным числом состояний, называется языком с конечным числом состояний. Структуру таких языков удобно изображать в виде графа, вершины которого сопоставлены S_j, а дуги —парам (m_i,S_q). На рис.1 приведен пример такого графа.

m₁

M={m₁,m₂,m₃}


S₁

S₂


m₀

m₁



S₀

S₅

m₁

m₂


m₃

m₃

m₃

Рис. 1

Рис. 2
Порождение цепочек символов можно рассматривать как результат работы некоторого гипотетического устройства (рис. 5.1.2). Вдоль бесконечной (в обе или в одну сторону) ленты, разделенной на клетки, перемещается управляющая головка (УГ). Заданы внешний (входной) алфавит М = {т₀, т₁, m₂ , ..., m_n }, символы которого называются буквами, внутренний алфавит S = {s₀, s₁, ..., s_r}, символы которого называются состояниями, и алфавит перемещений D = {П, Л, Н}. Все клетки ленты заполнены символами из М, по одному символу в каждой клетке. Символ т_о играет роль пустого символа (если в некоторой клетке стоит т_о, то “в клетке ничего не записано”). Предполагается, что вся бесконечная лента всегда заполнена символами то, за исключением тех клеток, где записаны какие-либо другие символы из М.

Управляющая головка может находиться в тех или иных состояниях, характеризуемых символами из S. Состояние s₀ особое. Если УГ находится в состоянии s₀, то “машина не производит никакой работы (выключена)”. Предполагается, что в конце работы машина всегда переходит в состояние s₀. В процессе работы машины УГ может перемещаться в дискретные такты времени вдоль ленты. Перемещение происходит либо на одну клетку вправо (П), либо на одну клетку влево (Л). Перемещение УГ в данный такт работы может отсутствовать (Н). В каждый такт работы УГ совершает следующие действия:

1) считывает символ m_i, (находящийся в клетке ленты, которую в этом такте “видит” УГ); 2) в соответствии со считанным символом m_i, и своим состоянием s_j, записывает символ m_i в эту клетку; 3) движется (не движется) вдоль ленты; 4) переходит в следующее состояние s_p. Всю работу машины можно задать с помощью функциональной таблицы Т, в клетках которой стоят тройки вида m_is_pd_l, где d_l D - символ, определяющий перемещение. Таким образом, функциональная таблица определяет отображение М х S в М х S х D. Содержательный смысл отображения (m_i, s_j)  (m_ks_pd_l) состоит в том, что, находясь в состоянии s_j, и считывая из клетки символ m_i, УГ записывает в данную клетку ленты символ m_i, переходит в состояние s_p и производит движение, определяемое символом d_l. Условимся, что функциональная таблица всегда устроена так, что имеет место отображение (т_i, s₀) (т_i, s₀, H). Это означает, что в “выключенном” состоянии машина не работает.

До начала функционирования машины необходимо заполнить (если это необходимо) некоторые клетки ленты символами, отличными от m₀, перевести УГ в состояние, отличное от s₀, и задать исходное положение УГ относительно ленты. После этого машина будет функционировать в соответствии с таблицей Т. Функционирование машины можно задать и с помощью графа, вершины которого взаимно однозначно соответствуют состояниям этого устройства, дуги — переходам из одного состояния в другое, при этом каждая дуга (s_j,s_p) взвешена парой (т_i, т_kd_l). Следуя Хомскому, часто состояние называют нетерминальным (вспомогательным) символом, символ m_i М — терминальным. Описанное гипотетическое устройство называется машиной Тьюринга.

Используя машину Тьюринга, уточним понятие алгоритма.

Понятие машины Тьюринга является строгим уточнением понятия алгоритма. Переход от интуитивного понятия алгоритма к точному понятию машины Тьюринга позволяет решить вопрос алгоритмической (машинной) разрешимости той или иной проблемы.

Один из первых отрицательных результатов был получен американским ученым Черчем в 1936 г. при рассмотрении проблемы распознавания выводимости в математической логике.

Определить для любых заданных формул R и S в логическом исчислении, существует ли дедуктивная цепочка, ведущая от R к S, или нет.

Если формула А может быть преобразована в формулу В однократным применением допустимой подстановки, и наоборот, то А и В — смежные формулы. Последовательность (A_i, i = 1, 2, ..., п) формул, соседние из которых смежны, называется дедуктивной цепочкой, ведущей от А₁ к А_n Под решением проблемы распознавания выводимости понимается алгоритм, дающий ответ на вопрос о существовании дедуктивной цепочки (для любых R и S).

Проблема является алгоритмически неразрешимой, если не существует алгоритма (соответствующей машины Тьюринга) для ее решения. Отдельная машина Тьюринга может быть представлена как программа произвольного вида для ЦВМ с потенциально бесконечной памятью.

Следуя Хомскому, введем ограничения на подстановки , прослеживая при этом соответствие полученной грамматики автоматическому устройству.

Ограничение 1. Если  удовлетворяет выражению (1.1),

т. е. является правилом вывода, то

Язык, порожденный грамматикой, удовлетворяющей (1.2), реализуется машиной Тьюринга.

О г р а н и ч е н и е 2. Если  - правило вывода, то (₁, ₂, a, (₁,₂,  - цепочки, а — отдельный символ;  не пусто)

((=₁a₂)&(₁₂)). (1.3)

Грамматики, удовлетворяющие соотношению (5.1.3), называются контекстными (контекстно связанными).

Контекстные грамматики реализуются устройствами типа автомата Майхилла.

Пусть (i,j, k, l, р) — одно из правил, определяющих работу автомата:

если блок управления находится в состоянии S_j, а считывающая головка — напротив клетки, содержащей символ т_i, то блок управления может перейти в состояние S_k, в то время как лента продвигается в l клеток влево, а рассматриваемый символ заменяется на т_p. Устройство, работающее по такому принципу, называется автоматом Майхилла.

Ограничение 3. Если  - правило вывода, то  - нетерминальная буква,  не пусто:

 (1.4)

Грамматика, удовлетворяющая (5.1.4), называется бесконтекстной (контекстно свободной).

Согласно (5.1.4), каждое правило грамматики утверждает, что определенный нетерминальный символ может быть заменен цепочкой символов независимо от контекста.

Язык, порождаемый бесконтекстной грамматикой, реализуется автоматом Майхилла специального вида, в котором используется магазинная память. Этот автомат, следуя Ньюэллу, Шоу и Саймону, будем называть магазинным автоматом.

Магазинный автомат представляет собой композицию управляющего автомата и трех магазинов, каждый из которых представляет собой бесконечную в одну сторону ленту. На ленте записано слово, первая буква которого записана в первой ячейке, вторая — во второй и т. д. При чтении воспринимается первая буква слова, затем она стирается и оставшаяся часть слова сдвигается к первой ячейке. При записи в магазин слова длины к. первые к. ячеек освобождаются в результате записанного ранее сдвига слова на к ячеек. Входной магазин связан с входными каналами управляющего автомата, выходной — с выходными каналами, внутренний магазин связан как с входными, так и выходными каналами управляющего автомата. Множество внутренних состояний управляющего автомата разбито на два подмножества: А и В. Если управляющий автомат находится в состоянии, принадлежащем подмножеству А, то происходит считывание информации из входного и внутреннего магазинов. Если автомат находится в состоянии S_i  В, то происходит считывание только из внутреннего магазина,

при этом автомат переходит в следующее состояние и записывает во внутренний и выходной магазины слова.

Правило бесконтекстной грамматики называется линейным, если оно имеет вид

АхВу, (1.5)

праволинейным, если

А  хВ, (1.6)

и леволинейным, если

Правило вида Ах называется заключительным. В зависимости от ограничений, определяемых правилами (5.1.5) — (5.1.7), бесконтекстная грамматика может быть:

а) линейной, если каждое ее незаключительное правило линейно, в частности оно леволинейно или праволинейно;

б) односторонне линейной, если каждое ее незаключительное правило леволинейно или каждое ее незаключительное правило праволинейно;

в) металинейной, если все ее незаключительные правила либо линейны, либо имеют вид S и если, кроме того, в ней нет правил вида А S ни для каких А,, , где ,  не пусты.

Односторонняя линейная грамматика реализуется конечным автоматом, и порождаемый ею язык называется конечноавтоматным.

Рассмотрим одностороннюю линейную грамматику, все правила которой праволинейные (для определенности) либо заключительные. Без потери общности можно предположить, что каждое линейное правило имеет вид А  аВ, где В — неначальный символ, и что каждое заключительное правило грамматики имеет вид А  а.

Пусть А₁, А₂, ..., A_n — нетерминальные символы грамматики, причем А₁ — начальный символ. Сопоставим грамматике конечный автомат, каждое внутреннее состояние которого взаимно однозначно соответствует нетерминальному символу грамматики, а входной символ — терминальному символу грамматики. При этом если A_i аА_j, — правило грамматики, то тройка (а, А_i, А_j) определяет функционирование автомата и понимается как переход от состояния А_i, в состояние А_j при считывании входного символа а (описание, при котором функции перехода и выхода всюду определены является полным описанием конечного автомата).

Для общности будем считать, что при переходе из состояния S_i в состояние S_j в результате входного воздействия а автомат вырабатывает на своем выходе символ Ь(список выходных символов конечного автомата представляет выходной алфавит конечного автомата). Тогда автомат можно определить как четверку (а, b,S_i,S_j).

Если фиксируется начальное состояние S₀, то автомат реализует оператор Т

который в дальнейшем будем называть автоматным.

Автоматный оператор Т (т.е действие конечного автомата) переводит входную последовательность символов (а_i) в выходную (b_i) в зависимости от начального состояния и реализуемой односторонней линейной грамматики. Автомат удобно представлять в виде функции T(диаграмма состояния автомата) на графе G = , каждой вершине которого взаимно однозначно соответствует состояние автомaта, и если из состояния S_i в состояние S_j автомат переходит в результате входного воздействия а, вырабатывая при этом выходной символ b, то соответствующие вершины v_i и v_j соединены дугой (v_i , v_j) взвешенной парой (а, Ь). Таким образом, областью определения этой функции Т является граф G = , построенный рассмотренным выше способом, а областью значений - входные, выходные символы и идентификаторы состояний автомата.

Р
(x,a)

(рис. 5.1.3). Если рассматривать автомат не как устройство, реализующее соответствующую грамматику, а изучать его строение (структуру), то следует представлять этот автомат не в виде машины Тьюринга, а в виде блок-схемы, изображенной на рис. 5.1.4, где М_x — множество входных терминальных символов; Му — множество выходных терминальных символов; Мz — множество нетерминальных символов (Мz = Мz⁺, Мz^-).


Mz^-={Z_i^-}


Память

Mz⁺={Z_i⁺}


S₂




(x,a)

(y,a)



Комбинационная часть


S₁

S₃

(x,b)

x_n

y_m

(y,b)

x₁

y₁


Рис. 3 Рис. 4

Машины Тьюринга.

Машина располагает конечным числом знаков (символов) s₁, s₂, ... ,s_k, образующих внешний(входной) алфавит, в котором кодируются сведения, подаваемые в машину, а также те, которые вырабатываются в ней. Для удобства принимают, что среди знаков внешнего алфавита имеется пустой знак (пусть это будет s₁), посылка которого в какую либо ячейку ленты (памяти) стирает тот знак, который раньше в ней хранился и оставляет ее пустой. На любой стадии работы машины в каждой ячейке хранится не более одного знака. Каждое сведение, хранящееся на ленте, изображается конечным набором знаков внешнего алфавита, отличных от пустого знака и хранящихся по одному в некоторых ячейках ленты. К началу работы машины на ленту подается начальная информация; работа машины складывается из следующих один за другим тактов, по ходу которых происходит преобразование начальной информации в промежуточные информации. Начальная информация может быть в виде любой конечной системы знаков внешнего алфавита, расставленной произвольно по ячейкам. Но в зависимости от того, какая была подана начальная информация U возможны два случая:

а) после конечного числа тактов машина останавливается, подавая сигнал об остановке; при этом на ленте оказывается изображенной некоторая информация B. В таком случае говорят, что машина применима к начальной информации U и перерабатывает ее в результирующую информацию B;

б) остановка и сигнал об остановке никогда не наступают. В таком случае говорят, что машина не применима к начальной информации U.

Говорят, что машина решает некоторый класс задач , если машина применима всегда к информации, изображающей в определенном коде условия любой отдельной задачи этого типа и перерабатывает ее в информацию, изображающую в том же коде решение этой задачи.

В машине Тьюринга система элементарных операций упрощена до предела: на каждом отдельном такте команда предписывает лишь замену единственного знака s_i хранящегося в обозреваемой ячейке, каким-либо другим знаком s_j. При i=j это означает, что содержание обозреваемой ячейки не меняется; при j=1 это означает, что если в обозреваемой ячейке хранился какой-либо знак, то он гасится. Дальнейшее упрощение заключается в том, что при переходе машины от одного такта к непосредственно следующему такту адрес обозреваемой ячейки может меняться не более, чем на одну единицу, т.е. обозревается соседняя слева или соседняя справа ячейка, или обозревается та же ячейка, что и предыдущем такте. Таким образом содержание какой-либо отдаленной ячейки отыскивается путем перебора подряд всех ячеек, пока не будет обнаружена нужная. Это очень удлиняет процесс, но возникает следующее удобство: в командах программы вместо произвольных адресов обозреваемых ячеек можно использовать только три стандартных адреса:

П - обозревать соседнюю справа ячейку,

Л - обозревать соседнюю слева ячейку,

Н - продолжать обозревать ту же ячейку.

В машине Тьюринга обработка информации происходит в логическом блоке, который может пребывать в одном из конечного числа состояний; пусть q_1, q₂, ... , q_m - специальные знаки введенные для обозначения этих состояний. Блок имеет два входных канала; по одному из них на каждой стадии работы машины поступает знак из обозреваемой ячейки, по другому - знак s_j, являющийся однозначной функцией от сигналов s_i, q, поданных на вход. Команды, обусловливающие срабатывание машины на каждом отдельном такте, имеют вид: Пq_l, Лq_l, Нq_l (l=1, 2, ..., m), где первый знак заменяет адрес обозреваемой ячейки, а второй предписывает логическому блоку надлежащее состояние. Знаки П, Л, Н, q₁, ..., q_m образуют внутренний алфавит машины.

Специфической особенностью машины Тьюринга является то, что на логический блок возлагается также выработка на каждом данном такте той команды, которая будет подаваться в блок управления к началу следующего такта. Следовательно, логический блок имеет, кроме канала для выдачи знака s_j, еще два канала для выдачи двух знаков очередной команды (см рис.5)

I

q₁

Z



H

q₂

Рис. 5

Выходная тройка знаков s_j, P, q_l (где Р - любой из трех знаков П, Л, Н) зависит только от того, какая входная пара знаков s_i, q_n , была подана в том же такте на входы блока. Т.е. логический блок реализует функцию, сопоставляющую каждой паре знаков s_i, q_n (всего таких пар km ) тройку знаков s_j, P, q_l. Такая функция называется логической функцией машины. Ее удобно изобразить в виде таблицы, столбцы которой занумерованы знаками состояний, а строки - знаками внешнего алфавита; в каждой ячейке записана соответствующая выходная тройка знаков, эта таблица называется функциональной схемой машины (см. Рис.6).

	q1	q2	q3	q4	q5
	Пq4	Лq3	Пq1	Лq5	Нq5
	Нq2	Нq1	Пq1	Лq1	Нq5
	Лq1	Пq2	Лq3	Пq4	Нq5
	Лq1	Пq2	Лq3	Пq4	Нq5

Рис. 6

Таким образом, работа машины Тьюринга вполне определяется той логической функцией, которую реализует логический блок, т.е. машины Тьюринга с общей функциональной схемой неразличимы. Структуру машины можно представить в виде следующей схемы:

I

I

I

I

I



Z

Q

P

q₁

z₂

Внешняя память машины изображена ячейками бесконечной ленты, предназначенной для хранения информации, закодированной в символах внешнего алфавита; внутренняя память - двумя ячейками для хранения очередной команды: Q - ячейка хранит знак состояния и Р - ячейка - знак сдвига. В этих двух ячейках происходит задержка знаков Р и q_i , полученных на выходе логического блока в данном такте работы, до начала следующего такта. Из Q-ячейки по линии обратной связи в логический блок поступает знак состояния q_i, выработанный этим же блоком в предыдущем такте. Из Р-ячейки знак сдвига направляется в механизм сдвига. Логический блок общается с внешней памятью посредством читающей и записывающей головки, в которой вмонтированы один входной канал (для считывания) и один выходной канал (для записи) логического блока ( на рис. головка изображена треугольником, установленным против “обозреваемой” ячейки). Функции управления заключаются в обеспечение сдвига не более, чем на одну ячейку, в соответствии с поступившим Р-знаком.

Итак, отличительными особенностями машины Тьюринга по сравнению с конечными автоматами (к которым относятся электронные вычислительные машины) являются:

1. В машине Тьюринга расчленение процесса на простые элементарные операции доведено до предельной возможности. Это значительно удлиняет процесс, но его логическая структура сильно упрощается и приобретает удобный для теоретических исследований стандартный вид.

2. В машине Тьюринга внешняя память изображается в виде неограниченной с обеих сторон ленты, разбитой на ячейки (очевидно, что это неосуществимо в реальной ЭВМ).

Вопросы на понимание содержания занятия

1. 
   Понятие конечного автомата.
   
2. 
   Что представляет собой внешняя и внутренняя память машины Тьюринга.
   
3. 
   В чем отличие конечного автомата от машины Тьюринга.
   

жүктеу/скачать 202.33 Kb.

Достарыңызбен бөлісу: