Регулярная грамматика и конечный автомат. (до 90 минут)

Любая регулярная грамматика может быть представлена взвешенным графом. В графе ; где K- множество концевых вершин (узлов), V – множество узлов, - множество дуг орграфа .

При этом

1) если А-грамматика имеет продукции вида B→аC, то узел орграфа, помеченный нетерминальным символом с помощью дуги, помеченной терминальным символом , соединяется с вершиной .

2) Если грамматика σ₃ имеет продукции вида B→а, то узел соединен дугой, помеченной символом , с концевой вершиной .

3) При наличии в А-грамматике правил вида В→Λ (где Λ – пустая цепочка, , ), каждый нетерминальный символ, для которого имеет место такое правило, считается концевой вершиной.

Пример: пусть .

Граф этой грамматики имеет вид

позволяющий записать порождаемый σ₃ язык α(σ₃), а предложениями α(σ₃) будут цепочки aa и bb. Действительно, деревья вывода следующие:

Эти предложения легко получаются из графа как последовательности весов дуг на пути от вершины J к вершине К (каждый такой путь соответствует одному из реальных деревьев вывода).

Примечание. Говорят, что конечный взвешенный орграф , имеющий один начальный узел и один или несколько конечных узлов, есть конечный автомат , распознающий язык (здесь - концевые вершины, q₁ – начальное состояние).

Пример. Пусть имеем диаграмму автоматной грамматики вида:

Очевидно, что имеем продукции Р={J→aJ, J→aB, B→bB, B→b}, порождающие язык .

Замечание. Графовое представление А-грамматики можно рассматривать не только как удобный аппарат порождения предложений соответствующего автоматного языка α(σ₃), но и как анализатор, распознающий слова, принадлежащие этому языку, и вырабатывающий их синтаксическую структуру.

Теорема. Для каждой автоматной грамматики σ₃ можно построить эквивалентный ей конечный распознающий автомат (анализатор) .

(доказательство на дом)

Лекция №20.

МАШИНЫ ТЬЮРИНГА КАК РАСПОЗНАВАТЕЛИ. (до 90 минут)

Продолжительность: 2 часа (90) минут

Ключевые (основные) вопросы (моменты)

Текст лекции

МАШИНЫ ТЬЮРИНГА КАК РАСПОЗНАВАТЕЛИ.

Машина Тьюринга – гипотетическая вычислительная машина, предложенная Аланом Тьюрингом в 1936 г. для уточнения эффективной процедуры (алгоритма) вычислений.

Первоначально машина Тьюринга – это автомат, обрабатывающий (пропуская команды в обоих направлениях) потенциально бесконечную ленту, разделенную на ячейки, в которых записаны по одному символы из конечного алфавита А (для дальнейшего примем, что пустой символ а₀ входит в этот алфавит, т. е. )

предполагается, что блок управления, являющийся конечным автоматом, имеет конечное число состояний Q={ q₀, q₁,…, q_n }, где q₀ – начальное (исходное) состояние блока.

Предполагается, что “программа” машины Тьюринга составляется из конечного множества команд вида: q_i a_j→ q_l a_k d_p, , где (и ).

Смысл команды следующий: блок управления, находясь в состоянии q_i после считывания головкой символа a_j из ячейки ленты должен перейти в состояние q_l головки, записать в обозреваемую ячейку символ a_k и передвинуть на один шаг d_p(d_p - влево, d_п - вправо, d_н - остаться неподвижной).

Говорят, что функция f: N₀^K® N_0, где N₀=NÈí0ý является вычислимой по Тьюрингу, если для каждого слова aÎ N₀^K справедливо утверждение, что при помещении некоторого представления aÎ N₀^K на ленту(и в предложение начального состояния) машина останавливается в случае считывания с ленты представления функции f(a).

Замечание:

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

В недетерминированной машине Тьюринга на каждой стадии вычислений существуют альтернативы.

2) на языке соответствий множество команд для рабочей недетерминированной машины Тьюринга есть отображение q=< M₁, M₂, S>, где

M₁= A* Q, M₂=A*Q*D, S: A*Q® A*Q*D, DomSÍ A*Q

(Если DomS= A*Q, то говорят о всюду определенной машине Тьюринга,

а если DomSÌ A*Q, то о частично определенной машине.)

J_mSÍ A*Q*D

При этом: если S=S_f, то машина Тьюринга является детерминированной, не всюду определенной машиной, а в случае S^|=Г_f (?)–детерминированной всюду определенной машиной.

Формально машина Тьюринга U_T есть кортеж <A, Q, Р>, где AÇQ=Ф и

A={a₀, a₁, a₂ … a_m} –внешний алфавит

Q={q₀ , q₁ , q₂ … q_n } –внутренний алфавит

Р- законы взаимодействия алфавитов А и Q.

В случай детерминированной машины Тьюринга ее законы взаимодействия символов Р представляют программу П(рассматривается как упорядоченной множество команд) и в этом случае записывают U_T= <A, Q, П >,

где П={ xÎP: q_ia_J® q_ea_Kd_p}

Как формальная система F.S. машина Тьюринга порождает множество своих конфигураций К (машинных слов вида d₁q_e a₂, где a₁ a₂ÎA*, q_eÎQ). Исходный объект – начальная конфигурация q₀ a₁ a₂ , правила Р- система команд. Особенность F.S., задающих алгоритм (в нашем случае машину Тьюринга), заключается в том, что в них любому порождаемому объекту (в нашем случае конфигурация машины Тьюринга) применимо одно правило. Именно это свойство обеспечивает детерминированность (однозначность) работы алгоритма.

Пример: Последовательность конфигураций машины Тьюринга <{ | a₀ +}, {q₁, q₂, q₃, q_z}>, реализующей в унарной системе счисления алгоритм сложения двух натуральных чисел следующий:

A\ Q	q1	q2	q3
|	a0dnq3	|d^ q2	|dnq3
a0	a0dnq1	a0dHq1	|dHq2
+	a0dnq2	+d^ q2	+dnq3

Конфигурация

№1 q₁=+|

q₁

a0

a0

|

|

|

+

|

|

|

|

a0

a0

q₁® a₀d_nq₃

№2 q₃=+|

k₁| k₂

a0

a0

a0

|

|

+

|

|

|

|

a0

a0

q₃

№9 (3+4+2)

q₃® |d_nq₃

||+|q₃

k₃| k₉

a0

a0

a0

|

|

+

|

|

|

|

a0

a0

q₃

№10 ||+|q₂

a₀q₃® |d_Hq₂

k₉| k₁₀

a0

a0

a0

|

|

+

|

|

|

|

a0

a0

q₂

№18 (2*(3+4+2))

||+||

a₀q₂® |d_^q₂

k₁₇| k₁₈

a0

a0

a0

|

|

+

|

|

|

|

|

a0

q₂

№19 a₀q₁ ||+||

a₀q₂® a₀d_nq₂

k₁₈| k₁₉

a0

a0

a0

|

|

+

|

|

|

|

|

q₁

№20

??® a₀d_nq₃

k₁₉| k₂₀

a0

a0

a0

a0

|

+

|

|

|

|

|

a0

q₃

№55

??® a₀d_nq₁

k₅₄| k₅₅

a0

a0

a0

a0

+

|

|

|

|

|

|

|

a0

№56

??® a₀d_nq₁(??)

k₅₅| k₅₆

a0

a0

a0

a0

??

|

|

|

|

|

|

|

a0

q₂

Пояснения: Из начальной конфигурации q₁+ сотрем самую левую палочку, машина Тьюринга (далее U_T) перейдет в состояние q₃ и передвинется по ленте вправо (см. в программе П верхнюю левую ячейку) т.к. реализована команда

|q₁®a₀d_nq_3. Затем U_T перейдет направо через все палочки и знак суммы +(см. в программе П верхнюю и нижнюю правые ячейки) до пустой ячейки a₀, поставит в ней палочку и перейдет в состояние q₂. Далее U_T, выполняя команды среднего столбца программы П перейдет влево, пока не окажется у пустой ячейки a₀. Переместившись на один шаг вправо, U_T перейдет в начальное состояние q₁, завершив тем самым первый цикл работы (число циклов равно трем). После третьего цикла U_T, попав в конфигурацию q₁+

Сотрет знак суммы + и перейдет в заключительное состояние qz (т.е. машина остановится0, а на ленте останется результат вычисления- семь палочек.   Примечания: 1) Рассмотренная машина Тьюринга существует для любого рекурсивно-перечислимого множество слов (цепочек) М(a)- слов a, порождаемых машиной при ее переходе из начального состояния q1 в заключительное qz, т.е d(q1,a)=qz. Однако, это не значит, что для любого такого множества М(a) может быть решена проблема распознавания. 2) Для того, чтобы машина Тьюринга существовала для любого рекурсивного автоматно-разрешимого множества слов(нужно не только построить порождающую слова машину (т.е. когда Т(a)=b), но и уметь определить такие a, обрабатывая которые она не может перейти в заключительное состояние qz= d(q1,a) (т.е. вычисляемое машиной Тьюринга значение функции на этих аргументах не определено). В общем случае эта проблема разрешима. Однако эта проблема оказывается разрешимой для некоторых классов машин Тьюринга – линейно-ограниченных, магазинных и конечных автоматов.   Напоминания: 1) Множество, характеристическая функция которого есть рекурсивная (вычислимая) функция, называется разрешимым (рекурсивным). 2) Множество значений рекурсивной функции называется перечислимым (рекурсивно-перечислимым)  

Лекция №21.

Дата добавления: 2015-12-01