Бильгаева Н.Ц. - Теория алгоритмов, формальных языков, грамматик и автоматов (1082244), страница 7
Текст из файла (страница 7)
Тем самымдоказывается, что если бы была разрешима новая задача, то можно было бы решить изаведомо неразрешимую задачу. Применяя метод сведения, обычно ссылаются наискусственные задачи, которые не представляют самостоятельного интереса, но длякоторых легко непосредственно доказать их разрешимость. К числу таких задач относитсяпроблема распознавания самоприменимости.Самоприменимыми называются алгоритмы, которые, начав работу над собственнымописанием, рано или поздно останавливаются. Если же алгоритм в таком случаезацикливается, он называется несамоприменимым. Аналогично можно говорить осамоприменимости машин Тьюринга, имея в виду их применение к своим линейнымизображениям.Таким образом, возникает задача: как узнать, является ли самоприменимым тот илииной алгоритм.Проблема распознавания самоприменимости алгоритмов состоит в том, чтобы найтиединый конструктивный прием, позволяющий за конечное число шагов по схеме любогоданного алгоритма узнать, является алгоритм самоприменимым или несамоприменимым.Доказательство того, что общего алгоритма распознавания самоприменимости несуществует, можно проводить, используя алгоритмические системы Тьюринга.
На основеэтого доказательства было показано, что проблема распознавания самоприменимостиалгоритмически неразрешима.3.11. Задания для самостоятельной работы1. Построить машину Тьюринга, выполняющую операцию конкатенации двух цепочек,заданных во входном алфавите А = {0, 1, *, ε}.2. Построить машину Тьюринга, выполняющую операцию копирования входнойцепочки, заданной в алфавите А = {1, *, ε }, где символ “*” используется в качестверазделителя двух цепочек.3. Построить машину Тьюринга в алфавите А={0, 1}, которая, начав работу с последнейединицы массива из единиц, сдвигает его на одну ячейку влево, не изменяя остальногосодержимого ленты.
Головка останавливается на первой единице перенесенного массива.4. По заданной совокупности команд машины Тьюринга Т и начальной конфигурации Кнайти заключительную конфигурацию.4.1.q01 → q01R,q10 → qz1E,q11 → q11L,q00 → q11R,а) К = 1101q001;б) К = 101q0010.4.2.q00 → q01L,q11 → q00R,q10 → qz0L,q01 → q11R,а) K = 1q1 0111; б) K = 1q11111.4.3.q10 → q11L,q00 → q10L,q11 → qz0R,q01 → q00R,а) K = 1000q1 01; б) K = 11q111101.5. Построить машину Тьюринга, которая во входной цепочке, заданной в алфавите А ={0, 1, ε}, переставляет единицы и нули так, чтобы все единицы были в начале, а нули в концецепочки.6. Построить композицию Т1⋅Т2 машин Тьюринга Т1 и Т2 по паре состояний (q1z, q20) инайти результат применения композиции Т1⋅Т2 к слову D.6.1.
Машины Т1 и Т2 заданы таблицами соответствия:T1:01q10q1z0Lq111Rq11q120Rq121Rq20q12q100Rq100Rq21T2:01q211Lq211Lа) D = 111100111011;q2z0Rq200Lб) D = 11010111.6.2. Машины Т1 и Т2 заданы таблицами соответствия:T1:T2:01q10q110Rq101Rq11q120Rq101Rq12q1z1L01q20q210Lq201Lq21q220Lq211Lq22q2z0Rq221Lа) D = 11000101001;б) D = 10100111110.7. Найти результат применения итерации машины Т по паре состояний (qz1, qi) к слову D.Заключительными состояниями машины Т являются qz1 и qz2. На ленте первоначальнозаписаны нули, а в начальной конфигурации головка указывает на левый символ входнойцепочки, состоящей из единиц.7.1.
Машина Тьюринга задана таблицей соответствия:T:01a) i = 1, D = 13k,q0qz10Eq10Rq1q30Eq20Rq2q40Eq00Rq3q41Rq4qz21Lб) i = 1, D = 13k+2, k ≥ 1.k ≥ 1;7.2. Машина Тьюринга задана таблицей соответствия:T:01a) i = 3, D = 12k+1, k ≥ 1;q0qz20Rq10Rq1qz20Rq20Rq2q30Rq21Rq3q41Lq10Eq4q50Lq41Lq5qz10Rq51Lб) i = 1, D = 13k+2, k ≥ 1.4. ФОРМАЛЬНЫЕ ГРАММАТИКИ И ЯЗЫКИ4.1. Общие сведенияВ последние три десятилетия появилось большое количество работ по общей теорииязыков и грамматик. Можно выделить четыре научных направления, которые удалосьобъединить по методам их исследования в одну общую задачу теории языков.Первое из этих направлений связано с построением формальной, или математической,лингвистики, которая начала особенно быстро развиваться в тот период, когда былисформулированы вопросы машинного перевода.
Эта проблема требовала формализациипонятий словарь, грамматика, язык, их классификации и умения относить конкретныесловари, грамматики, языки к определенному классу.Интерес к задачам такого рода еще более усилился с появлением искусственных языковпрограммирования. С появлением трансляторов проблема перевода во многом определилапостроение общей теории вычислительных машин, а сами языки программирования сталивсе более приближаться к формально построенным математическим конструкциям.Независимо от указанных двух направлений развивалось построение формальныхмоделей динамических систем. Для создания продуктивной теории эти модели должны былибыть, с одной стороны, достаточно узкими, а с другой - достаточно широкими, чтобыохватить некоторый общий класс прикладных задач.
Типичным примером такого родаявляется модель конечного автомата. Эта модель позволяет описать многие процессы,заданные на конечных множествах и развивающиеся в счетном времени, что позволилосоздать для нее продуктивную теорию. Если в эту модель ввести бесконечность по какомулибо параметру, то это приводит к общему классу систем, например, к машинам Тьюринга.Независимо и параллельно развивалась общая теория алгоритмов как ветвь современнойматематики. Развитие вычислительной техники поставило перед математической теориейалгоритмов новую задачу: стало необходимым классифицировать алгоритмы по различнымпризнакам. Эквивалентность понятий "алгоритм" и "машина Тьюринга" позволилапредположить, что поиски классификации алгоритмов окажутся связанными с поискамипромежуточных моделей между моделями конечного автомата и машиной Тьюринга.Таким образом, перечисленные четыре направления оказались тесно связанными.
Теорияязыков, порожденная чисто лингвистическими задачами, оказалась в центре интересовматематиков,занимающихсятеорией алгоритмов, и ученых, разрабатывающихабстрактные модели динамических систем и теоретические основы автоматики.Теория формальных языков и грамматик является разделом математическойлингвистики - специфической математической дисциплины,ориентированнойнаизучение структуры естественных и искусственных языков. По характеру используемогоматематического аппарата теория формальных грамматик и языков близка к теорииалгоритмов и теории автоматов.На интуитивном уровне язык можно определить как некоторое множество предложенийс заданной структурой, имеющих определенное значение. Правила, определяющиедопустимые конструкции языка, составляют синтаксис языка. Значение, или смысл фразы,определяется семантикой языка.Если бы все языки состояли из конечного числа предложений, то не было бы проблемысинтаксиса.
Но, так как язык содержит неограниченное (или довольно большое) числоправильно построенных фраз, то возникает проблема описания бесконечных языков спомощью каких-либо конечных средств.Различают следующие виды описания языков:1) порождающее, которое предполагает наличие алгоритма,последовательнопорождающего все правильные предложения языка;2) распознающее, которое предполагает наличие алгоритма, определяющегопринадлежность любой фразы данному языку.4.2. Основные понятия порождающих грамматикАлфавит - это непустое конечное множество. Элементы алфавита называютсясимволами.Цепочка над алфавитом Σ={а1, а2, …, аn} есть конечная последовательность элементоваi. Множество всех цепочек над алфавитом Σ обозначается Σ*.Длина цепочки х равна числу ее элементов и обозначается |x|. Цепочка нулевой длиныназывается пустой и обозначается символом ε.
Соответственно, непустая цепочкаопределяется как цепочка ненулевой длины. Пусть имеется алфавит Σ={а, b}. Тогдамножество всех цепочек определяется следующим образом: Σ*={ ε, а, b, aa, ab, ba, bb, aaa,aab, aba, . . .}.Цепочки x и y равны, если они одинаковой длины и совпадают с точностью до порядкасимволов, из которых они состоят.Над цепочками x и y определена операция сцепления (конкатенации, произведения),которая получается дописыванием символов цепочки y за символами цепочки x.Язык L над алфавитом Σ представляет собой множество цепочек над Σ. Необходиморазличать пустой язык L=0 и язык, содержащий только пустую цепочку: L={ε}≠0.Формальный язык L над алфавитом Σ - это язык, выделенный с помощью конечногомножества некоторых формальных правил.Пусть M и L - языки над алфавитами. Тогда конкатенация LM = {xyx∈L, y∈M}. Вчастности, {ε}L = L{ε}=L.
Используя понятие произведения, определим итерацию L* иусеченную итерацию L+ множества L:L+ =L* =∞iUL ,i =1∞iUL ,i =1где i - степень языка, L определяется рекурсивно следующим образом:L0 = {ε};L1 = L;Ln+1 = Ln L = L Ln;{ε}L=L{ε}=L.Например, если задан язык L={a}, тогда L*={ε, а, аа, ааа, …}, L+={a, aa, aaa, …}.Порождающая грамматика - это упорядоченная четверка G= (VT, VN, P, S), гдеVT - конечный алфавит, определяющий множество терминальных символов;VN - конечный алфавит, определяющий множество нетерминальных символов;Р - конечное множество правил вывода, т.е. множество пар следующего вида:u → v,где u, v ∈(VT∪VN)*;S - начальный символ (аксиома грамматики), S∈VN.Из терминальных символов состоят цепочки языка, порожденного грамматикой.Аксиомой называется символ в левой части первого правила вывода грамматики.Для того чтобы различать терминальные и нетерминальные символы, принятообозначать терминальные символы строчными, а нетерминальные символы заглавнымибуквами латинского алфавита.В грамматике G цепочка х непосредственно порождает цепочку у, если х = αuβ, у = αvβи u→v ∈ Р, т.е.
цепочка у непосредственно выводится из х, что обозначается х => у.Языком, порождаемым грамматикой G = (VT, VN, Р, S), называется множествотерминальных цепочек, выводимых в грамматике G из аксиомы:L(G) = {х | х ∈ VT*; S => *х}, где =>*- выводимость.Пример. Дана грамматика G = (VT, VN, Р, S), в которой VT = {а, b}, VN = {S}, Р = {S →aSb, S → ab). Определить язык, порождаемый этой грамматикой.Решение. Используя рекурсию, выведем несколько цепочек языка, порождаемого даннойграмматикой:S → ab;S → aSb => aabb;S → aSb =>aaSbb => aaabbb; . .
.Определим язык, порожденный данной грамматикой:L(G) = {anbn | n > 0}.Говоря о представлении грамматик, нужно отметить, что множество правил выводаграмматики может приводиться без специального указания множеств терминалов инетерминалов. В таком случае обычно предполагается, что грамматика содержит в точностите терминальные и нетерминальные символы, которые встречаются в правилах вывода.Также предполагается, что правые части правил, для которых совпадают левые части,можно записать в одну строку с использованием разделителя.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
