Теория автоматов. Учебное пособие. Теория автоматов Предмет теории автоматов
Теория автоматов
Теория автоматов - раздел дискретной математики , изучающий абстрактные автоматы - вычислительные машины, представленные в виде математических моделей - и задачи, которые они могут решать.
Теория автоматов наиболее тесно связана с теорией алгоритмов : автомат преобразует дискретную информацию по шагам в дискретные моменты времени и формирует результат по шагам заданного алгоритма .
Терминология
Символ - любой атомарный блок данных, который может производить эффект на машину. Чаще всего символ - это буква обычного языка, но может быть, к примеру, графическим элементом диаграммы.
- Слово - строка символов, создаваемая через конкатенацию (соединение).
- Алфавит - конечный набор различных символов (множество символов)
- Язык - множество слов, формируемых символами данного алфавита. Может быть конечным или бесконечным.
Говорят, что язык L читается (принимается) автоматом M, если он состоит из слов w на базе алфавита таких, что если эти слова вводятся в M, по окончанию обработки он приходит в одно из принимающих состояний F:
Обычно автомат переходит из состояния в состояние с помощью функции перехода , читая при этом один символ из ввода. Есть также автоматы, которые могут перейти в новое состояния без чтения символа. Функция перехода без чтения символа называется -переход (эпсилон-переход).
Применение
Практически теория автоматов применяется при разработке лексеров и парсеров для формальных языков (в том числе языков программирования), а также при построении компиляторов и разработке самих языков программирования.
Другое важнейшее применение теории автоматов - математически строгое нахождение разрешимости и сложности задач.
Типовые задачи
- Построение и минимизация автоматов - построение абстрактного автомата из заданного класса, решающего заданную задачу (принимающего заданный язык), возможно, с последующей минимизацией по числу состояний или числу переходов.
- Синтез автоматов - построение системы из заданных «элементарных автоматов», эквивалентную заданному автомату. Такой автомат называется структурным . Применяется, например, при синтезе цифровых электрических схем на заданной элементной базе.
См. также
Литература
- Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. - М .: Вильямс, 2002. - С. 528. - ISBN 0-201-44124-1
- Касьянов В. Н. Лекции по теории формальных языков, автоматов и сложности вычислений. - Новосибирск: НГУ, 1995. - C. 112.
Ссылки
Wikimedia Foundation . 2010 .
Смотреть что такое "Теория автоматов" в других словарях:
Теория автоматов
Теория автоматов - раздел теоретической кибернетики, который изучает математические модели (называемые здесь автоматами или машинами) реальных или возможных устройств, перерабатывающих дискретную информацию дискретными же тактами. Основными… … Экономико-математический словарь
теория автоматов - Раздел теоретической кибернетики, который изучает математические модели (называемые здесь автоматами или машинами) реальных или возможных устройств, перерабатывающих дискретную информацию дискретными же тактами. Основными понятиями этой теории… … Справочник технического переводчика
Сущ., кол во синонимов: 1 тавт (1) Словарь синонимов ASIS. В.Н. Тришин. 2013 … Словарь синонимов
теория автоматов - automatų teorija statusas T sritis automatika atitikmenys: angl. automata theory vok. Automatentheorie, f rus. теория автоматов, f pranc. théorie des automates, f … Automatikos terminų žodynas
У этого термина существуют и другие значения, см. Диаграмма состояний. Диаграмма состояний ориентированный граф для конечного автомата, в котором вершины обозначают состояния дуги показывают переходы между двумя состояниями На практике… … Википедия
Теория машин и механизмов (ТММ) это научная дисциплина об общих методах исследования, построения, кинематики и динамики механизмов и машин и о научных основах их проектирования. Содержание 1 История развития дисциплины 2 Основные понятия … Википедия
ТЕОРИЯ - (1) система научных идей и принципов, обобщающих практический опыт, отражающих объективные природные закономерности и положения, которые образуют (см.) или раздел какой либо науки, а также совокупность правил в области какого либо знания млн.… … Большая политехническая энциклопедия
Теория алгоритмов Экономико-математический словарь
Теория алгоритмов - раздел математики, изучающий общие свойства алгоритмов. Проблема построения алгоритма с теми или иными свойствами называется алгоритмической проблемой, ее неразрешимость означает отсутствие соответствующего алгоритма; если… … Экономико-математический словарь
Книги
- Теория автоматов. Учебник для бакалавриата и магистратуры , Кудрявцев В.Б.. Учебник содержит обширный материал по теории автоматов. В нем вводится понятие автомата, даны теории…
Вычислительные машины, представленные в виде математических моделей - и задачи, которые они могут решать.
Теория автоматов наиболее тесно связана с теорией алгоритмов : автомат преобразует дискретную информацию по шагам в дискретные моменты времени и формирует результат по шагам заданного алгоритма .
Энциклопедичный YouTube
1 / 3
✪ Урок 12. Основы теории автоматов. Математическая логика. Уроки по информатике
✪ Как управлять миром, изучив всего одну простую модель!
✪ Урок 15. Решение прикладных задач по теории автоматов. Математическая логика. Уроки по информатике
Субтитры
Терминология
Символ - любой атомарный блок данных, который может производить эффект на машину. Чаще всего символ - это буква обычного языка, но может быть, к примеру, графическим элементом диаграммы.
- Слово - строка символов, создаваемая через конкатенацию (соединение).
- Алфавит - конечный набор различных символов (множество символов)
- Язык - множество слов, формируемых символами данного алфавита. Может быть конечным или бесконечным .
Говорят, что язык L читается (принимается) автоматом M, если он состоит из слов w на базе алфавита Σ {\displaystyle \Sigma } таких, что если эти слова вводятся в M, по окончанию обработки он приходит в одно из принимающих состояний F:
L = { w ∈ Σ ⋆ | δ ^ (S 0 , w) ∈ F } {\displaystyle L=\{w\in \Sigma ^{\star }|{\hat {\delta }}(S_{0},w)\in F\}}Обычно автомат переходит из состояния в состояние с помощью функции перехода δ {\displaystyle \delta } , читая при этом один символ из ввода. Есть автоматы, которые могут перейти в новое состояние без чтения символа. Функция перехода без чтения символа называется ϵ {\displaystyle \epsilon } -переход (эпсилон-переход).сложности задач.
Типовые задачи
- Построение и минимизация автоматов - построение абстрактного автомата из заданного класса, решающего заданную задачу (принимающего заданный язык), возможно, с последующей минимизацией по числу состояний или числу переходов.
- Синтез автоматов - построение системы из заданных «элементарных автоматов», эквивалентной заданному автомату. Такой автомат называется структурным . Применяется, например, при синтезе цифровых электрических схем на заданной элементной базе.
Все рассмотренные выше устройства относятся к классу комбинационных схем, то есть дискретных устройств без памяти. Наряду с ними в цифровой технике широкое распространение получили последовательностные автоматы, или, иначе, комбинационные схемы, объединенные с элементами памяти.
Под термином автомат можно понимать некоторое реально существующее устройство, функционирующее на основании как сигналов о состоянии внешней среды, так и внутренних сигналов о состоянии самого автомата. В этом плане ЭВМ может быть рассмотрена как цифровой автомат. Под цифровым автоматом понимается устройство, предназначенное для преобразования цифровой информации. С другой стороны, под термином автомат можно понимать математическую модель некоторого устройства. Общая теория автоматов подразделяется на две части: абстрактную и структурную теорию автоматов. Различие между ними состоит в том, что абстрактная теория абстрагируется от структуры как самого автомата, так и входных и выходных сигналов. В абстрактной теории анализируются переходы автомата под воздействием абстрактных входных слов и формируемые на этих переходах абстрактные выходные слова.
В структурной теории рассматривается структура как самого автомата, так и его входных и выходных сигналов, способы построения автоматов из элементарных автоматов, способы кодирования входных и выходных сигналов, состояний автомата.
В соответствии с этим принято различать две модели автоматов: структурную и абстрактную. Абстрактная модель применяется при теоретическом рассмотрении автоматов. Структурная модель служит для построения схемы автомата из логических элементов и триггеров и предназначена для выполнения функции управления.
Абстрактный автомат – это математическая модель цифрового автомата, задаваемая шестикомпонентным вектором S=(A,Z,W,d,l,a 1), где А={a a ,…,a m } – множество внутренних состояний абстрактного автомата; Z=; «Труды математического института им. В. А. Стеклова АН СССР», 1958, т. 51; Глушков В. М. Синтез цифровых автоматов. М., 1962 [библиогр. с. 464- 469]; Кобр инский Н. Е., Трахтенброт Б. А. Введение в теорию конечных автоматов. М., 1962 [библиогр. с. 399-402]; Цетлин М. Л. Исследования по теории автоматов и моделированию биологических систем. М., 1969 [библиогр. с. 306-316]; Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы (Поведение и синтез). М., 1970 [библиогр. с. 389-395]; Автоматы. Пер. с англ. М., 1956. Б. А, Трахтенброт.