Введение в теорию автоматов, языков и вычислений. Глава 11.


ГЛАВА 11 Дополнительные классы проблем Труднорешаемые проблемы не ограничиваются классом MP. Существует много других классов труднорешаемых проблем, по разным причинам представляющих интерес. Не­которые вопросы, связанные с этими классами, вроде V = MP, остаются нерешенными. Дж.Хопкрофт — Введение в теорию автоматов. Глава 1-2 Дж.Хопкрофт — Введение в теорию автоматов. Глава 3-5 Дж.Хопкрофт — Введение в теорию Читать далее

Введение в теорию автоматов, языков и вычислений. Глава 10.


ГЛАВА 10 Труднорешаемые проблемы Обсуждение вычислимости переносится на уровень ее эффективности или неэффектив­ности. Предметом изучения становятся разрешимые проблемы, и нас интересует, какие из них можно решить на машинах Тьюринга за время, полиномиально зависящее от раз­мера входных данных. Напомним два важных факта из раздела 8.6.3.

Введение в теорию автоматов, языков и вычислений. Глава 9.


ГЛАВА 9 Неразрешимость Эта глава начинается повторением рассуждений из раздела 8.1, которые неформально обосновывали существование проблем, не разрешимых с помощью компьютера. Недос­татком тех «правдоподобных рассуждений» было вынужденное пренебрежение реаль­ными ограничениями, возникающими при реализации языка С (или другого языка про­граммирования) на любом реальном компьютере. Однако эти ограничения, вроде конеч­ности адресного пространства, не являются фундаментальными. Наоборот, с Читать далее

Введение в теорию автоматов, языков и вычислений. Глава 8.


ГЛАВА 8. Введение в теорию машин Тьюринга В этой главе направление наших усилий меняется. До сих пор нас интересовали в основ­ном простые классы языков и пути их использования для относительно ограниченных задач, вроде анализа протоколов, поиска в текстах или синтаксического анализа. Теперь начнется исследование языков, которые вообще можно определить с помощью вычисли­тельных устройств. Это равносильно изучению Читать далее

Введение в теорию автоматов, языков и вычислений. Глава 7.


ГЛАВА 7 Свойства контекстно- свободных языков Наше изучение контекстно-свободных языков завершается знакомством с некоторыми из их свойств. Вначале определяются ограничения на структуру продукций КС-грамматик и доказывается, что всякий КС-язык имеет грамматику специального вида. Этот факт об­легчает доказательство утверждений о КС-языках.

Введение в теорию автоматов, языков и вычислений. Глава 6.


ГЛАВА 6 Автоматы с магазинной памятью Контекстно-свободные языки задаются автоматами определенного типа. Такой автомат называется автоматом с магазинной памятью, или магазинным автоматом, и является расширением недетерминированного конечного автомата с f-переходами, представляю­щего собой один из способов определения регулярных языков. Магазинный автомат — это, по существу, е-НКА с добавлением магазина. Магазин может читаться, в его верши­ну могут Читать далее

Введение в теорию автоматов, языков и вычислений. Глава 5.


ГЛАВА 5 Контекстно-свободные грамматики и языки Перейдем от рассмотрения регулярных языков к более широкому классу языков, которые называются контекстно-свободными. Они имеют естественное рекурсивное описание в ви­де контекстно-свободных грамматик. Эти грамматики играют главную роль в технологии компиляции с начала 1960-х годов; они превратили непростую задачу реализации синтак­сических анализаторов, распознающих структуру программы, из неформальной в рутин­ную, которую можно решить Читать далее

Введение в теорию автоматов, языков и вычислений. Глава 4.


ГЛАВА 4 Свойства регулярных языков В этой главе рассматриваются свойства регулярных языков. В разделе 4.1 предлагается инструмент для доказательства нерегулярности некоторых языков — теорема, которая называется «леммой о накачке» («pumping lemma»).

Введение в теорию автоматов, языков и вычислений. Глава 3.


ГЛАВА 3 Регулярные выражения и языки В этой главе вводится система записи «регулярных выражений». Такие выражения пред­ставляют собой еще один способ определения языков, рассмотренный вкратце в разде­ле 1.1.2. Регулярные выражения можно рассматривать также как «язык программирова­ния» для описания некоторых важных приложений, например, программ текстового поиска или компонентов компилятора. Регулярные выражения тесно связаны с НКА и Читать далее

Введение в теорию автоматов, языков и вычислений. Глава 2.


ГЛАВА 2 Конечные автоматы В этой главе мы введем класс языков, известных как «регулярные». Это языки, которые могут быть описаны конечными автоматами. Последние мы уже обсудили вкратце в разделе 1.1.1. Перед тем как формально определить конечные автоматы, рассмотрим развернутый пример, из которого станет ясной мотивация последующего изучения этих объектов.

Введение в теорию автоматов, языков и вычислений. Глава 1.


Предисловие В предисловии к своей книге 1979 года, предшествовавшей данному изданию, Дж. Хопкрофт и Дж. Ульман с удивлением отмечали, что за время, прошедшее после выхода их первой книги в 1969 году, произошел взрыв в развитии теории автоматов. Действительно, книга, вышедшая в 1979 году, содержала множество тем, не затронутых в предыдущей работе, и по объему была Читать далее

Введение в теорию автоматов, языков и вычислений


2-Е ИЗДАНИЕ. ДЖОН ХОПКРОФТ РАДЖИВ МОТВАНИ ДЖЕФФРИ УЛЬМАН. Перевод с английского О. И. Васылык, М. Саит-Аметова, канд.физ.-мат.наук А.Б. Ставровского Под редакцией канд.физ.-мат.наук А. Б. Ставровского Книга известных американских ученых посвящена теории автоматов и соответст¬вующих формальных языков и грамматик — как регулярных, так и контекстно- свободных. Во второй части рассматриваются различные машины Тьюринга, при помо¬щи которых формализуются Читать далее

Баранов. Введение в теорию автоматов.


Глава третья КОДИРОВАНИЕ СОСТОЯНИЙ АВТОМАТА 3-1. Гонки в автомате Как уже отмечалось во второй главе, задача кодирования состоя­ний является одной из основных задач канонического метода струк­турного синтеза автоматов. Напомним, что кодирование заключается в сопоставлении с каждым состоянием автомата набора состояний эле­ментарных автоматов памяти одинаковой длины I (в данном параграфе для простоты ограничимся использованием в качестве Читать далее

Выхованец В.С. Сборник задач по теории автоматов.


Выхованец В.С. Сборник задач по теории автоматов Учебное пособие для вузов. Оглавление ПРЕДИСЛОВИЕ…………………………………………………………………………………………………………………………………………………….. 2 Раздел 1. Формальные языки и грамматики…………………………………………………………………………………. 3 СКАЧАТЬ! Выхованец В.С. Теория автоматов Учеб. пособие для вузов Выхованец В.С. Теория автоматов/

ФОРМАЛЬНЫЕ ЯЗЫКИ И ГРАММАТИКИ


«В начале было слово…» Бытие, 1,1 Определение. ТЕОРИЯ АВТОМАТОВ – это раздел дискретной математики, изучающей математические модели дискретных преобразователей информации.

ФОРМАЛЬНЫЕ ЯЗЫКИ


Определение. ЗНАК – это элемент конечного множества различных элементов. Пример. +,-,*

ОПЕРАЦИИ НАД СТРОКАМИ


1. Операция конкатенации строк (соединение строк). Пусть заданы строки принадлежащие множеству над алфавитом .

ФОРМАЛЬНЫЕ ГРАММАТИКИ


Определение. ФОРИАЛЬНОЙ ГРАММАТИКОЙ называется формальная система, состоящая из четырех объектов , где

КЛАССИФИКАЦИЯ ГРАММАТИК


КЛАССИФИКАЦИЯ ГРАММАТИК ПО ХОМСКОМУ. Общепринятой классификацией грамматик и порождаемых ими языков является иерархия Хомского, содержащая четыре типа грамматик.

ПОРАЖДЕНИЕ ЯЗЫКОВ ГРАММАТИКАМИ.


Формальные языки классифицируются по типу грамматики, которая их порождает, то есть язык, порожденный грамматикой типа 0, называется языком типа 0. Язык, порожденный грамматикой типа 1, называется языком типа

О е-свободной грамматике.


Для произвольной КС грамматики существует эквивалентная ей КС грамматика такая, что . То есть язык порождаемый КС грамматикой эквивалентен языку порождаемому КС грамматикой с точностью до пустой строки. Очевидно, что КС грамматика не содержит продукций вида .

ЦЕПНЫЕ ПРОДУКЦИИ


Определение. ЦЕПНОЙ ПРОДУКЦИЕЙ называется продукция вида. ТЕОРЕМА 1.2. О КС грамматике без цепных продукций. Для произвольной КС грамматике содержащей цепные продукции вида , где существует эквивалентная ей КС грамматика не содержащая цепных продукций.

ПРИВЕДЕНИЕ КС ГРАММАТИК


Определение. ДОСТИЖИМЫМ(ВЫВОДИМЫМ) нетерминальным знаком называется такой нетерминальный знак , что в грамматике существует вывод ;  

РАЗРЕШИМОСТЬ ЯЗЫКОВ


Под РАЗРЕШИМОСТЬЮ ЯЗЫКОВ понимается распознавание принадлежности произвольной строки языку, заданному формальной грамматикой .

О разрешимости проблемы пустоты КС языка.


Если — КС грамматика, то разрешима проблема пустоты языка . ДОКАЗАТЕЛЬСТВО. Применим к КС грамматике эффективную процедуру приведения КС грамматики. Если получена КС грамматика у которой аксиома — производящий знак, то язык не пуст. В противном случае язык пуст.

НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ ДЛЯ ГРАММАТИКИ.


Определение. НЕРАЗРЕШИМОЙ ПРОБЛЕМОЙ называется отсутствие эффективной процедуры решения некоторой задачи для наперед неизвестной грамматики .

О неразрешимых проблемах для КС грамматик.


Если и КС грамматики, то неразрешимыми проблемами являются: 1. Пусто ли пересечение КС языков? То есть , или нет? 2. Является ли КС языком пересечение КС языков? То есть если и КС грамматики и , -КС язык или нет?

МАШИНА ТЬЮРИНГА


Определение. МАШИНОЙ ТЬЮРИНГА называется формальная система (устройство), задаваемое четверкой объектов , где — конечный алфавит ленты,