Теория автоматов. 2.Автоматы как распознаватели. Конечный автомат

Языки могут быть заданы двумя способами:

1) грамматиками (порождающее средство языка);

2) автоматами (распознающее средство языка).

Распознователи — автоматные грамматики.

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

Внешняя память отсутствует.

Конечный автомат — простейший тип автоматов, который имеет входную ленту, с которой за один такт может быть считан один входной символ, это односторонний распознаватель, на каждом такте движется вправо (не может оставаться на месте), вн. память отсутствует.

Вид: А = (Q, T, δ, p0, F), где:

Q - конечное мн-во сост-ий;

T - алфавит (входной);

δ - функция переходов;

p0 - начальное сост-е;

F - мн-во заключит.сост-ий.

Функцию переходов удобно задавать таблицей.

Автомат с магазинной памятью (МП-автомат) имеет внешнюю память (рабочую ленту), которая организована в виде стека (магазина).

МП-автомат - это семерка вида: R = (Q, T, M, δ, q₀, F, m₀), где

Q - конечное множество состояний;

T — алфавит входной;

M — алфавит памяти (магазина);

δ - функция переходов;

q₀ - начальное состояние;

F - множество заключительных состояний;

m₀ - символ из множества Г для обозначения маркера дна магазина.

В общем случае данное определение соответствует недетерминированному автомату.

В отличие от конечного автомата для произвольного МП-автомата нельзя построить

эквивалентный детерминированный автомат.