ГЛАВА 10 Труднорешаемые проблемы Обсуждение вычислимости переносится на уровень ее эффективности или неэффективности. Предметом изучения становятся разрешимые проблемы, и нас интересует, какие из них можно решить на машинах Тьюринга за время, полиномиально зависящее от размера входных данных. Напомним два важных факта из раздела 8.6.3.
ГЛАВА 9 Неразрешимость Эта глава начинается повторением рассуждений из раздела 8.1, которые неформально обосновывали существование проблем, не разрешимых с помощью компьютера. Недостатком тех «правдоподобных рассуждений» было вынужденное пренебрежение реальными ограничениями, возникающими при реализации языка С (или другого языка программирования) на любом реальном компьютере. Однако эти ограничения, вроде конечности адресного пространства, не являются фундаментальными. Наоборот, с Читать далее
ГЛАВА 8. Введение в теорию машин Тьюринга В этой главе направление наших усилий меняется. До сих пор нас интересовали в основном простые классы языков и пути их использования для относительно ограниченных задач, вроде анализа протоколов, поиска в текстах или синтаксического анализа. Теперь начнется исследование языков, которые вообще можно определить с помощью вычислительных устройств. Это равносильно изучению Читать далее
ГЛАВА 7 Свойства контекстно- свободных языков Наше изучение контекстно-свободных языков завершается знакомством с некоторыми из их свойств. Вначале определяются ограничения на структуру продукций КС-грамматик и доказывается, что всякий КС-язык имеет грамматику специального вида. Этот факт облегчает доказательство утверждений о КС-языках.
ГЛАВА 6 Автоматы с магазинной памятью Контекстно-свободные языки задаются автоматами определенного типа. Такой автомат называется автоматом с магазинной памятью, или магазинным автоматом, и является расширением недетерминированного конечного автомата с f-переходами, представляющего собой один из способов определения регулярных языков. Магазинный автомат — это, по существу, е-НКА с добавлением магазина. Магазин может читаться, в его вершину могут Читать далее
ГЛАВА 5 Контекстно-свободные грамматики и языки Перейдем от рассмотрения регулярных языков к более широкому классу языков, которые называются контекстно-свободными. Они имеют естественное рекурсивное описание в виде контекстно-свободных грамматик. Эти грамматики играют главную роль в технологии компиляции с начала 1960-х годов; они превратили непростую задачу реализации синтаксических анализаторов, распознающих структуру программы, из неформальной в рутинную, которую можно решить Читать далее
ГЛАВА 4 Свойства регулярных языков В этой главе рассматриваются свойства регулярных языков. В разделе 4.1 предлагается инструмент для доказательства нерегулярности некоторых языков — теорема, которая называется «леммой о накачке» («pumping lemma»).
ГЛАВА 3 Регулярные выражения и языки В этой главе вводится система записи «регулярных выражений». Такие выражения представляют собой еще один способ определения языков, рассмотренный вкратце в разделе 1.1.2. Регулярные выражения можно рассматривать также как «язык программирования» для описания некоторых важных приложений, например, программ текстового поиска или компонентов компилятора. Регулярные выражения тесно связаны с НКА и Читать далее
ГЛАВА 2 Конечные автоматы В этой главе мы введем класс языков, известных как «регулярные». Это языки, которые могут быть описаны конечными автоматами. Последние мы уже обсудили вкратце в разделе 1.1.1. Перед тем как формально определить конечные автоматы, рассмотрим развернутый пример, из которого станет ясной мотивация последующего изучения этих объектов.
Предисловие В предисловии к своей книге 1979 года, предшествовавшей данному изданию, Дж. Хопкрофт и Дж. Ульман с удивлением отмечали, что за время, прошедшее после выхода их первой книги в 1969 году, произошел взрыв в развитии теории автоматов. Действительно, книга, вышедшая в 1979 году, содержала множество тем, не затронутых в предыдущей работе, и по объему была Читать далее
2-Е ИЗДАНИЕ. ДЖОН ХОПКРОФТ РАДЖИВ МОТВАНИ ДЖЕФФРИ УЛЬМАН. Перевод с английского О. И. Васылык, М. Саит-Аметова, канд.физ.-мат.наук А.Б. Ставровского Под редакцией канд.физ.-мат.наук А. Б. Ставровского Книга известных американских ученых посвящена теории автоматов и соответст¬вующих формальных языков и грамматик — как регулярных, так и контекстно- свободных. Во второй части рассматриваются различные машины Тьюринга, при помо¬щи которых формализуются Читать далее
Файл Token.cs using System; using System.Collections.Generic; using System.Collections; using System.Text; namespace ТЯП_лб2_м6 { enum TokenType { ERROR =0, Num, Identificator, BracketLeft, BracketRight, Not, End, Assign, OperatorBoolean};
using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; using System.IO;
Приднестровский государственный университет им. Т.Г. Шевченко Инженерно технический институт Кафедра ВКСС Выполнил:Студент гр.05В(сокр.) Д.И.Ивченко Проверил:Преподаватель кафедры ВКСС О.И.Вакарь Тирасполь 2007 СОДЕРЖАНИЕ
1.Написать программу, которая вычисляет среднее арифметическое действительных элементов массива без учета минимального и максимального элементов массива.
1. В программе вводятся по очереди символьные строки. Количество букв ‘а’ в этих строках подсчитывается в функции, и это число возвращается в основную программу. Конец ввода строк это ввод нулевой строки.
Описание предметной области Информационная система «Таксопарк» предназначена для упрощения регулированием системы и для автоматизации её функций. Таксопарк «Миг» является современным автотранспортным предприятием, которое оказывает услуги по перевозке людей на легковых автомобилях. Для состоятельных клиентов предусмотренная дополнительная услуга – VIP карта, которая позволяет накапливать скидку и оплачивать поездки со своего счета. Если поездка осуществляется одним клиентом Читать далее
КОНТРОЛЬНАЯ РАБОТА №1 по «Информатике» для студентов 1 курса заочного отделения специальности ВКСС инженерно-технического института Разработала: Ст.преп. кафедры ПОВТ и АСФурдуй Ольга Михайловна Тирасполь, 2008
1. Написать функцию, которая возвращает максимальное из двух целых чисел, полученных в качестве аргумента.
Что такое трансляция, компиляция, транслятор, компилятор? Трансляция программы — преобразование программы, представленной на одном из языков программирования, в программу на другом языке и, в определённом смысле, равносильную первой. Язык, на котором представлена входная программа, называется исходным языком, а сама программа — исходным кодом. Выходной язык называется целевым языком или объектным кодом. Понятие трансляции относится не Читать далее
1 Вопрос: Что такое таблица символов и для чего она предназначена? Таблица символов – это таблица состоящая из набора полей, количество которых равно числу идентификаторов программы. Каждое поле содержит в себе полную информацию о данном элементе таблицы.
Номер задания выбирается в соответствии с номером в списке студентов в журнале группы. Контрольная работа состоит из двух частей – теоретической и практической. В первой части нужно представить развернутый письменный ответ на теоретический вопрос.
Глава третья КОДИРОВАНИЕ СОСТОЯНИЙ АВТОМАТА 3-1. Гонки в автомате Как уже отмечалось во второй главе, задача кодирования состояний является одной из основных задач канонического метода структурного синтеза автоматов. Напомним, что кодирование заключается в сопоставлении с каждым состоянием автомата набора состояний элементарных автоматов памяти одинаковой длины I (в данном параграфе для простоты ограничимся использованием в качестве Читать далее
ТЕОРИЯ АВТОМАТОВ Задания контрольной работы, вопросы к экзамену и список литературы для студентов-заочников 3-го курса специальности «ВКСС»
Выхованец В.С. Сборник задач по теории автоматов Учебное пособие для вузов. Оглавление ПРЕДИСЛОВИЕ…………………………………………………………………………………………………………………………………………………….. 2 Раздел 1. Формальные языки и грамматики…………………………………………………………………………………. 3 СКАЧАТЬ! Выхованец В.С. Теория автоматов Учеб. пособие для вузов Выхованец В.С. Теория автоматов/
ПРИДНЕСТРОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. Т.Г.ШЕВЧЕНКО Инженерно-технический институт Кафедра «Информационных технологий и автоматизированного управления производственными процессами» Для студентов очной и заочной форм обучения по направлению 655800 – «Пищевая инженерия» Издательство Приднестровского университета Тирасполь 2009 Долгов Ю.А. – Основы математического моделирования: Учебное пособие. – Тирасполь: Изд-во Приднестр. ун-та, 2009. – 102 c. (в обл.)
Лабораторная работа № 7 Цель работы — выработать навыки обработки результатов пассивного эксперимента для нахождения математической модели исследуемого объекта с помощью метода наименьших квадратов с предварительной ортогонализацией факторов.
Лабораторная работа № 6 Цель работы — выработать навыки обработки результатов пассивного эксперимента для нахождения математической модели исследуемого объекта с помощью модифицированного метода случайного баланса.
Лабораторная работа № 4 Цель работы: привить навыки по обработке экспериментальных данных, представленных в виде специально оформленной таблицы, которая построена по блочному принципу, а также навыки по выделению группы наиболее сильно влияющих факторов эксперимента.
Лабораторная работа № 3 Цель работы — привить навыки по обработке полученных экспериментальным путем статистических данных для определения мер тесноты связи случайных величин, а также определения уравнений регрессии по методу Чебышева.
