Теория автоматов
Учебная работа Учебную работу возглавляет заместитель директора по учебной работе — Оболоник Екатерина Федоровна, отличник народного образования ПМР, руководитель высшей квалификационной категории, преподаватель естественных дисциплин, высшей квалификационной категории.
ГЛАВА 11 Дополнительные классы проблем Труднорешаемые проблемы не ограничиваются классом MP. Существует много других классов труднорешаемых проблем, по разным причинам представляющих интерес. Некоторые вопросы, связанные с этими классами, вроде V = MP, остаются нерешенными. Дж.Хопкрофт — Введение в теорию автоматов. Глава 1-2 Дж.Хопкрофт — Введение в теорию автоматов. Глава 3-5 Дж.Хопкрофт — Введение в теорию Читать далее
ГЛАВА 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-Е ИЗДАНИЕ. ДЖОН ХОПКРОФТ РАДЖИВ МОТВАНИ ДЖЕФФРИ УЛЬМАН. Перевод с английского О. И. Васылык, М. Саит-Аметова, канд.физ.-мат.наук А.Б. Ставровского Под редакцией канд.физ.-мат.наук А. Б. Ставровского Книга известных американских ученых посвящена теории автоматов и соответст¬вующих формальных языков и грамматик — как регулярных, так и контекстно- свободных. Во второй части рассматриваются различные машины Тьюринга, при помо¬щи которых формализуются Читать далее
Глава третья КОДИРОВАНИЕ СОСТОЯНИЙ АВТОМАТА 3-1. Гонки в автомате Как уже отмечалось во второй главе, задача кодирования состояний является одной из основных задач канонического метода структурного синтеза автоматов. Напомним, что кодирование заключается в сопоставлении с каждым состоянием автомата набора состояний элементарных автоматов памяти одинаковой длины I (в данном параграфе для простоты ограничимся использованием в качестве Читать далее
ТЕОРИЯ АВТОМАТОВ Задания контрольной работы, вопросы к экзамену и список литературы для студентов-заочников 3-го курса специальности «ВКСС»
Выхованец В.С. Сборник задач по теории автоматов Учебное пособие для вузов. Оглавление ПРЕДИСЛОВИЕ…………………………………………………………………………………………………………………………………………………….. 2 Раздел 1. Формальные языки и грамматики…………………………………………………………………………………. 3 СКАЧАТЬ! Выхованец В.С. Теория автоматов Учеб. пособие для вузов Выхованец В.С. Теория автоматов/
Что такое вычислительный центр, какие бывают компьютеры, как они устроены, почему учат работать с компьютером в школе – обо всем этом и многом другом расскажет данный сайт. Красочные иллюстрации помогут понять и усвоить основные принципы работы компьютеров Как рассматривать этот сайт? Да, вообще-то его можно рассматривать, как и любой другой. Но можно и иначе. Этот Читать далее
Когда наш предок впервые взял палку, чтобы сбить плод с дерева, он удлинил свою руку. Когда человек придумал рычаг, чтобы сдвинуть тяжелый камень, он увеличил свою физическую силу. Подзорная труба увеличила зоркость человека, а велосипед увеличил его скорость. Но человек на этом не остановился. Рычаг сменил мощный подъемный кран, подзорную трубу заменил телескоп, на смену Читать далее
«С голубого ручейка начинается река…» Компьютерная река тоже началась с «ручейка», точнее – с нескольких ручейков. Они нарисованы на картинке. Левый ручеек – это различные технические устройства, с помощью которых люди увеличивали скорость счета. Средний – машины и механизмы, где использовались принципы программирования. Справа собраны научные открытия, использовавшиеся потом при создании компьютеров. Слившись вместе, эти Читать далее
Пекарь из муки и воды в специальной печи выпекает хлеб. Токарь из бесформенной болванки на станке делает болты и гайки. Столяр из обыкновенного полена может сделать Буратино. Человек, работающий на компьютере, из информации делает информацию.
Компьютер – это машина для обработки информации. Информация для него и исходное сырье, и конечный продукт. Поэтому у любого компьютера должны быть устройства, через которые в него поступает информация; устройства, где она хранится и обрабатывается, и, наконец, устройства, предназначенные для вывода результатов.
Компьютер может многое: считать, писать, рисовать. Может говорить, исполнять музыку (Сто профессий компьютера.). Но все эти сложные действия обязательно дробятся на самые простые: сложение, вычитание, сравнение. И производит эти действия центральный процессор. Всё, что обрабатывает центральный процессор, поступает в него из оперативной памяти. В это «всё» входят как сами числа, которые нужно обрабатывать, так и Читать далее
Для хранения информации в компьютерах используются разные устройства. Отличаются они емкостью памяти и временем доступа к ней (Как устроен компьютер.). Хранилища информации уже сравнивались с книгой, лежащей на столе, с книжным шкафом в комнате. Можно добавить еще библиотеку, где книжных шкафов намного больше, чем в комнате. Зато, чтобы получить книгу из библиотеки, и времени надо Читать далее
Представь себе пишущую машинку. Только вместо листа бумаги – телеэкран. Нажал клавишу – и буква появилась на экране. Это и есть дисплей. Работать с дисплеем не труднее, чем с обыкновенной пишущей машинкой. Правда, клавиш побольше и есть еще дополнительные переключатели. Благодаря им каждая клавиша может дать не два символа, как на машинке, а четыре. Кроме Читать далее
Для ввода информации в компьютер служат разные устройства: лентопротяжные механизмы, дисководы, каналы связи. Для ручного ввода информации, пожалуй, самое удобное – дисплей (Дисплеи.). На дисплее есть клавиатура, как на пишущей машинке. С нее очень удобно вводить тексты.
Ты уже знаешь, что клавиатура не единственное средство ввода информации в компьютер. Есть и сколка, и мышка… (Сколка, мышка и джойстик.). Но все это хорошо для ввода графической информации: чертежей, рисунков. А как быть с речью? И нужно ли это? Мысль о говорящем и слушающем компьютере владела учеными давно, почти с рождения вычислительных машин. Однако Читать далее
Раньше люди писали на глиняных табличках, писали на бересте, на шелке. В течение последних столетий для этих целей служила бумага. Продолжает служить и сейчас, в век компьютеров. Потому что, хоть магнитные и лазерные носители информации (Кладовые памяти.) и «емче» бумажных, человек не может ими пользоваться без помощи технических средств. Для того же, чтобы прочесть то, Читать далее
Если ты собираешься использовать компьютер как игротеку, или как набор карандашей для рисования, то для этого никаких особых знаний не требуется. Достаточно ознакомиться с клавиатурой, выучить назначение нескольких клавиш – и всё. Остальное компьютер подскажет сам.
Компьютер – система очень сложная. Состоит он из разных компонент (Как устроен компьютер.) – центрального процессора, оперативной и внешней памяти, дисплеев, принтеров… И все эти устройства должны работать согласованно, как один механизм.
Таким должен быть автомобиль? А это смотря для чего его использовать. Если нужно перевозить тонны руды или песка, то лучше всего это делать на огромных КамАЗах и БелАЗах. Чтобы перевозить небольшие партии груза, берут «рафик» или УАЗ. Для личного пользования служат «Москвичи», «Жигули» и «Запорожцы». Так же обстоит дело и с компьютерами. Их выбор определяется Читать далее
