Category Archives for Теория автоматов

«Многие вещи нам не понятны не потому, что наши понятия слабы, но потому, что сие вещи не входят в круг наших понятий» К. Прутков.

Определение. МАШИНОЙ ТЬЮРИНГА называется формальная система (устройство), задаваемое четверкой объектов , где — конечный алфавит ленты,

Всякий алгоритм может быть реализован машиной Тьюринга. То есть, если машины Тьюринга не реализует данный алгоритм, то этот алгоритм вовсе не алгоритм.

Систему команд машины Тьюринга можно интерпретировать как описание работы некоторого устройства или как программу. До сих пор мы воспринимали машину Тьюринга как программу, выступая в роли некоторого устройства, интерпретирующего эту программу. Все ли одинаково выполняют эту интерпретацию?

Стоит задача определения результативности алгоритма, которая является необходимым условием для реализации. Определение. РЕЗУЛЬТАТИВНОСТЬ – есть получение результата за конечное время (конечное число шагов).

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

Никакое нетривиальное свойство вычислимых функций не является алгоритмически разрешимым.

Определение. ДАТЕРМЕНИРОВАННОЙ МАШИНОЙ ТЬЮРИНГА называется такая машина Тьюринга, у которой отображение множества декартового произведения множеств алфавита ленты и состояния устройства управления в множество декартового произведения множеств алфавита ленты, состояния устройства управления и множества перемещения ленты – функционально, то есть не существует двух одинаковых команд в множестве с одинаковой левой частью.

Сеть Петри представляет собой модель дискретных систем. Дадим неформальное определение сети Петри.

1. “Возбуждение переходов”. Те переходы, которые имеют входящие дуги от позиций, содержащих метки, возбуждаются, то есть способны к функционированию (срабатыванию). В примере возбуждаются преходы .

Формализация функционирования сетей Петри заключается в последовательной смене ее маркировок.

Класс терминальных языков сетей Петри: 1. Строго мощнее, чем класс языков, порождаемых регулярными грамматиками .

Определение. МАГАЗИННЫМ АВТОМАТОМ называется формальная система состоящая из 5 (6) объектов , где — конечный алфавит входных знаков;

Для любого языка, порождаемого КС грамматикой существует магазинный автомат, возможно недетерминированный, распознающий (принимающий) строки этого языка. То есть для любого существует такой , что .

Если — язык, принимаемый некоторым, возможно недетерминированным магазинным автоматом , то этот язык может быть порожден КС грамматикой, то есть существует грамматика , такая что .

Для любого непустого регулярного языка , порождаемого регулярной грамматикой , существует конечный автомат , возможно недетерминированный, представляющий (порождающий и распознающий) язык .

«Tempora mutantur, et nos mutamur in illis” (Времена меняются, и мы меняемся вместе с ними) Латинский афоризм

определение: 1. Конечный автомат будем представлять как пятерку объектов: -, где входной алфавит ; — алфавит (множество) состояний содержит n элементов, начиная с нуля ; — выходной алфавит ; -отображения (функция) переходов ; — отображения (функция) выходов

Формулировка: Для любого конечного автомата существует неотличимый от него минимальный автомат единственный с точностью до изоморфизма, имеющий состояний, если множество состояний автомата разбивается на классов эквивалентности . 

a) Пусть задан автомат и известно, что число его состояний . b) Зададим начальное приближение классов эквивалентности и сделаем это следующим образом: два состояния и относим в один класс эквивалентности , если и только если для всех входных знаков . 

Утверждение: Для любого автомата Мили существует неотличимый от него автомат Мура . Доказательство:

Алгебра регулярных событий. Пусть заданы два языка и над некоторым алфавитом . Введем три операции: 1. объединение языков 2. конкатенация языков  

Утверждение: Любой язык, построенный в алгебре регулярных событий (заданный регулярным событием) является языком порождаемым регулярной грамматикой.

Утверждение: Для любого регулярного выражения существует конечный автомат представляющий (распознающий, порождающий) язык, задаваемый этим выражением.

Утверждение: Для любого регулярного выражения существует источник представляющий тот же язык .

Определение 2:асинхронный автомат (источник) — называется такой конечный автомат (источник) у которого все состояния (вершины) устойчивы по каждому входному знаку.

Самый отдаленный пункт… к чему-нибудь да близок, а самый близкий – от чего-нибудь да отдален. Козьма Прутков.

Определение: Комбинационный автомат- это конечный автомат, у которого выходной знак зависит от входного, и не зависит от состояния автомата. 

Пусть задан некоторый конечный автомат К Вопрос : Как представить автомат в виде автоматной сети, возможно состоящий из более простых автоматов, чем исходных ? 

Как было показано ранее, комбинационный автомат может быть представлен в виде автомата с одним состоянием и реализует некоторую дискретную функцию.