Гинзбург Сеймур. Математическая теория контекстно-свободных языков

формат djvu
размер 3.64 МБ
добавлен 15 октября 2011 г.

Москва, "Мир", 1970-326 стр. Перевод с английского
В книге достаточно полно изложены основные понятия и результаты теории контекстно-свободных грамматик и языков, прослеживаются ее связи с теорией автоматов, языками программирования, лингвистикой и машинным переводом.
Имеется большое число упражнений самой различной трудности, которые в совокупности существенно дополняют основной текст книги.
Книга окажется полезной математику, желающему ознакомиться с теорией формальных грамматик и ее связями с другими математическими теориями.
Контекстно-свободные языки и языки ТИПА АЛГОЛ
Языки, порождаемые грамматиками
Языки типа АЛГОЛ
Эквивалентность КС-языков и языков типа АЛГОЛ
Вспомогательные утверждения
Деревья выводов
Неопределенность
Подстановка
Неукорачивающие КС-грамматики
Автоматы и языки
Конечные автоматы и регулярные множества
Линейные правила
КС-языки специального вида
Автоматы с магазинной памятью
Характеристика КС-языков в терминах МП-автоматов
Детерминированные КС-языки
Операции над кс-языками
Языки, не являющиеся контекстно-свободными
Пересечение и разность
Последовательностные преобразования
Характеристика конечного преобразования
Преобразователи с магазинной памятью
Некоторые специальные операции
Нормальная форма КС-языка
Алгоритмические проблемы
Алгоритмически разрешимые проблемы
Основные алгоритмически неразрешимые проблемы
Алгоритмические проблемы, связанные с конечными преобразованиями
Алгоритмические проблемы, связанные с МП-преобразователями
Неразрешимость проблемы распознавания определенности КС-грамматики
Ограниченные кс-языки
Основные понятия
Теорема Парика
Структура ограниченных КС-языков
Характеристики ограниченных КС-языков
Распознавание ограниченности КС-языка
Другие алгоритмические проблемы
Существенная неопределенность
Существенно неопределенные КС-языки, содержащиеся во множестве а* . an
Ограниченные существенно неопределенные КС-языки
Алгоритмическая неразрешимость проблемы распознавания существенной неопределенности
Приложение
Библиография
Предметный указатель

Похожие разделы

Смотрите также

Арбиб М.А. Алгебраическая теория автоматов, языков и полугрупп

формат djvu
размер 3.6 МБ
добавлен 10 ноября 2010 г.

Издательство: Статистика, 1975, 335 c. Монография посвящена рассмотрению математического аппарата количественного и качественного анализа АСУ. Конечные автоматы благодаря их простой реализуемости на ЭВМ имеют значительные преимущества по сравнению с другими моделями. Авторы знакомят читателей с основными достижениями в этой области. Книга рассчитана на разработчиков АСУ и цифровых средств вычислительной техники, на математиков, работающих в обл...

Выхованец В.С. Теория автоматов

формат pdf
размер 1.25 МБ
добавлен 19 сентября 2010 г.

Учеб. пособие для вузов. - Тирасполь, 2001. 120 с. В учебном пособии излагаются основы современной теории автоматов, представляющих собой одну из основных моделей управляющих систем. Рассматриваются вопросы, связанные с формальными языками и грамматиками, общей теорией алгоритмов, магазинными и конечными автоматами. Представлен прикладной аспект проектирования дискретных устройств. Формальные языки и грамматики Формальные языки Формальные граммат...

Гросс М., Лантен А. Теория формальных грамматик

формат djv
размер 7.07 МБ
добавлен 14 марта 2010 г.

М.: Мир, 1971. - 296 с. Книга посвящена одной из наиболее важных областей математической лингвистики - теории формальных грамматик Хомского. В первой части вводятся необходимые понятия из алгебры, математической логики и теории алгоритмов. Во второй рассматриваются некоторые классы формальных языков; третья часть посвящена алгебраической трактовке языков и их свойств. Написанная на достаточно высоком уровне строгости, книга в то же время является...

Дехтярь М.И. Конечные автоматы (Лекции по дискретной математике)

формат pdf
размер 475.64 КБ
добавлен 06 ноября 2010 г.

Содержание Переработка информации с помощью конечных автоматов Конечные автоматы распознаватели Детерминированные конечные автоматы (ДКА) и автоматные языки Произведение автоматов Недетерминированные конечные автоматы и их детерминизация Регулярные выражения и языки Регулярные языки и конечные автоматы Автоматы для регулярных языков Свойства замкнутости класса автоматных языков Теорема о разрастании автоматных языков. Неавтоматные языки

Пентус А.Е., Пентус М.Р. Теория формальных языков

формат pdf
размер 539.73 КБ
добавлен 10 февраля 2010 г.

М.: Издательство ЦПИ при механико-математическом факультете МГУ, 2004. - 80 с. Учебное пособие посвящено классическому разделу математической лингвистики и теоретической информатики - теории формальных языков. Рассматриваются порождающие грамматики, классификация формальных языков по Хомскому, регулярные выражения, конечные автоматы, автоматы с магазинной памятью, алгоритмические проблемы, связанные с контекстно-свободными грамматиками. Для студе...

Рейуорд-Смит В.Дж. Теория формальных языков. Вводный курс

формат djvu
размер 2.12 МБ
добавлен 17 сентября 2009 г.

М.: Радио и связь, 1988. - 128 с. В книге автора из Великобритании изложены основы теории формальных языков. Использован математический аппарат теории множеств, теории графов и математической логики. Все сведения, необходимые для понимания рассмотренных в книге вопросов, приведены в соответствующих главах. Удачно подобранные упражнения в конце каждой главы не только поясняют, но и дополняют основной материал книги. Для разработчиков программного...

Самостоятельная работа №1

Лабораторная

формат doc
размер 52.34 КБ
добавлен 22 мая 2006 г.

Представление грамматики конечным автоматом и сетью Петри. Изучение способов задания языков грамматиками, распознающими автоматами, сетями Петри и построение конечного автомата, распознающего заданный язык.

Самостоятельная работа №1 (2)

Лабораторная

формат doc
размер 53.19 КБ
добавлен 23 мая 2006 г.

Хопкрофт Д., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений

формат djvu
размер 3.88 МБ
добавлен 15 июня 2009 г.

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

Шпоры по теории автоматов

pottee

формат doc
размер 401.11 КБ
добавлен 30 мая 2006 г.

Строки. Префиксы, суффиксы, подстроки. Языки. Форма Бэкуса-Наура. Дерево вывода. Синтаксические и семантические деревья. Замыкание Клини. Контекстная грамматика. Контекстно-свободная гр-ка(КС/Г). Регулярные языки. Порождающие грамматики. Виды, примеры. Классификация языков по Хомскому. Примеры. Регулярные грамматики и конечный автомат. Автоматы и теория алгоритмов. Распознавание мн-в автоматами. Распознаватели, задачи, виды распознавателей. Машин...