Автоматом называется формальная система имеющая входной и выходной каналы данных и находящийся в каждый из дискретный момент времени в одном из конечного числа состояний.

Потребуем, чтобы множество входных сигналов, выходных сигналов и внутренних состояний было конечным.

Концепция порождения и распознавания.

Автомат-акцептор – это абстракция автомата, при которой он рас­сматривает как устройство, которое может отличать ко­нечные последовательности входных данных с помощью своих состояний (концепция распознавания).

Порождающий автомат — это абстракция автомата, при которой он рас­сматривает как устройство, порождающее последовательность сообщений на выходе при переходе из одного состояния в другое.

Автомат-преобразователь — это абстрактный автомат, при кото­ром он рассматривает как устройство преобразующее последова­тельность входных сообщений в последовательность выходных сообщений, при этом автомат изменяет свое состояние. Пример: компилятор.

Формальной грамматикой G называется алгебраическая система G = < V, W, P, I > , где

V — алфавит терминальных знаков (основных) ,

W — алфавит не­терминальных знаков (вспомогательных) , (изначально предполагается, что V?W=?);

P — множество продук­ций (где правило вывода имеет вид P = {a®b, a, b? ( V ? W )*} ,

I — аксиома грамматики (начальный знак) , I ? W

Формальным языком L, порожденным формальной грамматикой G , L=L(G), называется всевозможные строки в терминальном алфавите, которые могут быть выведены из аксиомы грамматики: L(G)={t ? V* | I^G ? t}

Классификация грамматик и автоматов:

1)Грамматика типа 0 (произвольная) , имеет особенность, что на всю продукцию этой грамматики не накладыва­ется никаких ограничений: a®b , a ? (V?W)⁺ , b ? (V?W)* .

Тезис Поста утверждает, что каждая грамматик типа 0 может быть реализована в виде МТ.

2.1) Грамматика типа 1 (контекстная). Для контекстных грамматик произвольная продукция имеет следующий вид: a А b ® a w b; a, b, w? (V?W)* ; A ? W*.

2.2) Грамматика типа 1` (полуконтекстная). Это грамматика вида:

а) a А ® a w ; a, b ? (V?W)* ; A ? W*. – правосторонняя контекстная грамматика;

б) А b ® w b ; b, w ? (V?W)* ; A ? W*.– левосторонняя контекстная грамматика;

a — левый, b — правый контекст.

Контекстной грамматике соответствует Машина Майхилла. Задается командами: (q_i, a_j ® q_i^|, a_j^|, l_k ) где l _k ? N и говорит на сколько позиций смещается лента влево (и только влево) или на одну вправо.

3) Грамматика типа 2 (контекстно-свободная), продукции которой имеют вид :

А® a , A?W , a ? (V?W)*

Контекстно-свободная — магазинный автомат, представляющий собой некоторое устройство управление, имеется полу — лента справа и слева и стек. Используется: 1) для распознавания строк принадлежащих некоторой грамматике. 2) Порождение строк принадлежащих некоторому языку (генерация кода). 3) Объединения задача распознавания и порождения для организации процесса компиляции . М=<V,Q,A,P,B,I>, где V- входной алфавит, Q — множество состояний, A — внутренний алфавит стека, P — отображения Q?V (Q?V?A ® Q?A?B), B — выходной алфавит, I- начальная конфигурация

4) Грамматика типа 3 (регулярная) : это грамматика, продукции которой имеют вид :

а) А® а | aB – правосторонняя;

б) А® а | Bа – левосторонняя; где a ? V ; A ,B ? W

Пример регулярной грамматики: двоичные целые числа I®0 | 1 | I1 | I0 | A; A®+ | — | e

Регулярная грамматика соответствует конечному автомату. A ? W, a ? V ; A®a ; A®aB — левосторонний вывод, A®Ba — правосторонний вывод.