Успенский В.А. Машина Поста

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

Алгоритмические модели. Машина Тьюринга. Основная гипотеза Тьюринга. Устойчивость автоматов. Состязания и гонки конечных автоматов. ры по устранению гонок в структурном автомате. Направленное кодирование состояний абстрактного автомат. Cоседние кодирование соседних состояний. Синхронизация структурного автомата. Двойная память. Абстрактный автомат и способы его задания. Детерминированность и способы задания МТ. Конфигурация МТ. Канонический мето...

Настоящая книга является переводом сборника статей по теории автоматов. Это - молодая научная дисциплина (отрасль кибернетики), возникшая под влиянием запросов техники цифровых вычислительных машин и моделирующих устройств. Сборник отражает различные аспекты теории автоматов. Некоторые статьи посвящены вопросам, связанным с конструированием автоматов. Другие интересы главным образом с теоретико-познавательной точки зрения. СОДЕРЖАНИЕ: ЧАСТЬ I:...

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