Читайте также: |
|
Любая регулярная грамматика может быть представлена взвешенным графом. В графе ; где K- множество концевых вершин (узлов), V – множество узлов, - множество дуг орграфа .
При этом
1) если А-грамматика имеет продукции вида B→аC, то узел орграфа, помеченный нетерминальным символом с помощью дуги, помеченной терминальным символом , соединяется с вершиной .
2) Если грамматика σ3 имеет продукции вида B→а, то узел соединен дугой, помеченной символом , с концевой вершиной .
3) При наличии в А-грамматике правил вида В→Λ (где Λ – пустая цепочка, , ), каждый нетерминальный символ, для которого имеет место такое правило, считается концевой вершиной.
Пример: пусть .
Граф этой грамматики имеет вид
позволяющий записать порождаемый σ3 язык α(σ3), а предложениями α(σ3) будут цепочки aa и bb. Действительно, деревья вывода следующие:
Эти предложения легко получаются из графа как последовательности весов дуг на пути от вершины J к вершине К (каждый такой путь соответствует одному из реальных деревьев вывода).
Примечание. Говорят, что конечный взвешенный орграф , имеющий один начальный узел и один или несколько конечных узлов, есть конечный автомат , распознающий язык (здесь - концевые вершины, q1 – начальное состояние).
Пример. Пусть имеем диаграмму автоматной грамматики вида:
Очевидно, что имеем продукции Р={J→aJ, J→aB, B→bB, B→b}, порождающие язык .
Замечание. Графовое представление А-грамматики можно рассматривать не только как удобный аппарат порождения предложений соответствующего автоматного языка α(σ3), но и как анализатор, распознающий слова, принадлежащие этому языку, и вырабатывающий их синтаксическую структуру.
Теорема. Для каждой автоматной грамматики σ3 можно построить эквивалентный ей конечный распознающий автомат (анализатор) .
(доказательство на дом)
Лекция №20.
МАШИНЫ ТЬЮРИНГА КАК РАСПОЗНАВАТЕЛИ. (до 90 минут)
Продолжительность: 2 часа (90) минут
Ключевые (основные) вопросы (моменты)
Текст лекции
МАШИНЫ ТЬЮРИНГА КАК РАСПОЗНАВАТЕЛИ.
Машина Тьюринга – гипотетическая вычислительная машина, предложенная Аланом Тьюрингом в 1936 г. для уточнения эффективной процедуры (алгоритма) вычислений.
Первоначально машина Тьюринга – это автомат, обрабатывающий (пропуская команды в обоих направлениях) потенциально бесконечную ленту, разделенную на ячейки, в которых записаны по одному символы из конечного алфавита А (для дальнейшего примем, что пустой символ а0 входит в этот алфавит, т. е. )
предполагается, что блок управления, являющийся конечным автоматом, имеет конечное число состояний Q={ q0, q1,…, qn }, где q0 – начальное (исходное) состояние блока.
Предполагается, что “программа” машины Тьюринга составляется из конечного множества команд вида: qi aj→ ql ak dp, , где (и ).
Смысл команды следующий: блок управления, находясь в состоянии qi после считывания головкой символа aj из ячейки ленты должен перейти в состояние ql головки, записать в обозреваемую ячейку символ ak и передвинуть на один шаг dp(dp - влево, dп - вправо, dн - остаться неподвижной).
Говорят, что функция f: N0K® N0, где N0=NÈí0ý является вычислимой по Тьюрингу, если для каждого слова aÎ N0K справедливо утверждение, что при помещении некоторого представления aÎ N0K на ленту(и в предложение начального состояния) машина останавливается в случае считывания с ленты представления функции f(a).
Замечание:
При изучении моделей вычислений обычно проводят различие между детерминированными и недетерминированными алгоритмами. В детерминированной машине Тьюринга общий ход вычислений полностью определяется ее программой, начальным состоянием и записанными на ленте словами.
В недетерминированной машине Тьюринга на каждой стадии вычислений существуют альтернативы.
2) на языке соответствий множество команд для рабочей недетерминированной машины Тьюринга есть отображение q=< M1, M2, S>, где
M1= A* Q, M2=A*Q*D, S: A*Q® A*Q*D, DomSÍ A*Q
(Если DomS= A*Q, то говорят о всюду определенной машине Тьюринга,
а если DomSÌ A*Q, то о частично определенной машине.)
JmSÍ A*Q*D
При этом: если S=Sf, то машина Тьюринга является детерминированной, не всюду определенной машиной, а в случае S|=Гf (?)–детерминированной всюду определенной машиной.
Формально машина Тьюринга UT есть кортеж <A, Q, Р>, где AÇQ=Ф и
A={a0, a1, a2 … am} –внешний алфавит
Q={q0 , q1 , q2 … qn } –внутренний алфавит
Р- законы взаимодействия алфавитов А и Q.
В случай детерминированной машины Тьюринга ее законы взаимодействия символов Р представляют программу П(рассматривается как упорядоченной множество команд) и в этом случае записывают UT= <A, Q, П >,
где П={ xÎP: qiaJ® qeaKdp}
Как формальная система F.S. машина Тьюринга порождает множество своих конфигураций К (машинных слов вида d1qe a2, где a1 a2ÎA*, qeÎQ). Исходный объект – начальная конфигурация q0 a1 a2 , правила Р- система команд. Особенность F.S., задающих алгоритм (в нашем случае машину Тьюринга), заключается в том, что в них любому порождаемому объекту (в нашем случае конфигурация машины Тьюринга) применимо одно правило. Именно это свойство обеспечивает детерминированность (однозначность) работы алгоритма.
Пример: Последовательность конфигураций машины Тьюринга <{ | a0 +}, {q1, q2, q3, qz}>, реализующей в унарной системе счисления алгоритм сложения двух натуральных чисел следующий:
A\ Q | q1 | q2 | q3 |
| | a0dnq3 | |d^ q2 | |dnq3 |
a0 | a0dnq1 | a0dHq1 | |dHq2 |
+ | a0dnq2 | +d^ q2 | +dnq3 |
Конфигурация
№1 q1=+|
q1
a0 | a0 | | | | | | | + | | | | | | | | | a0 | a0 |
|
k1| k2
a0 | a0 | a0 | | | | | + | | | | | | | | | a0 | a0 |
q3
№9 (3+4+2)
|
k3| k9
a0 | a0 | a0 | | | | | + | | | | | | | | | a0 | a0 |
q3
№10 ||+|q2
|
k9| k10
a0 | a0 | a0 | | | | | + | | | | | | | | | a0 | a0 |
q2
№18 (2*(3+4+2))
||+||
|
k17| k18
a0 | a0 | a0 | | | | | + | | | | | | | | | | | a0 |
q2
№19 a0q1 ||+||
|
k18| k19
a0 | a0 | a0 | | | | | + | | | | | | | | | | |
q1
№20
|
k19| k20
a0 | a0 | a0 | a0 | | | + | | | | | | | | | | | a0 |
q3
№55
|
k54| k55
a0 | a0 | a0 | a0 | + | | | | | | | | | | | | | | | a0 |
№56
|
k55| k56
a0 | a0 | a0 | a0 | ?? | | | | | | | | | | | | | | | a0 |
q2
Пояснения: Из начальной конфигурации q1+ сотрем самую левую палочку, машина Тьюринга (далее UT) перейдет в состояние q3 и передвинется по ленте вправо (см. в программе П верхнюю левую ячейку) т.к. реализована команда
|q1®a0dnq3. Затем UT перейдет направо через все палочки и знак суммы +(см. в программе П верхнюю и нижнюю правые ячейки) до пустой ячейки a0, поставит в ней палочку и перейдет в состояние q2. Далее UT, выполняя команды среднего столбца программы П перейдет влево, пока не окажется у пустой ячейки a0. Переместившись на один шаг вправо, UT перейдет в начальное состояние q1, завершив тем самым первый цикл работы (число циклов равно трем). После третьего цикла UT, попав в конфигурацию q1+
Сотрет знак суммы + и перейдет в заключительное состояние 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; просмотров: 27 | Нарушение авторских прав