Теория формальных грамматик и автоматов;

Пусть задан алфавит V.

Теория формальных грамматик и автоматов; - student2.ru — множество всех слов в алфавите V.

Формальный язык L в алфавите V — произвольное подмножество Теория формальных грамматик и автоматов; - student2.ru .

Теория формальных грамматик и автоматов; - student2.ru —грамматика, где

V — основной алфавит;

W — вспомогательный алфавит;

Теория формальных грамматик и автоматов; - student2.ru

I — начальный символ, Теория формальных грамматик и автоматов; - student2.ru ;

R — множество правил вывода, вида Теория формальных грамматик и автоматов; - student2.ru , где Теория формальных грамматик и автоматов; - student2.ru .

Теория формальных грамматик и автоматов; - student2.ru   Теория формальных грамматик и автоматов; - student2.ru слово b есть непосредственное следствие слова a, если Теория формальных грамматик и автоматов; - student2.ru , Теория формальных грамматик и автоматов; - student2.ru и существует правило Теория формальных грамматик и автоматов; - student2.ru слово b выводимо из слова a, если существует последовательность слов Теория формальных грамматик и автоматов; - student2.ru такая что для всех Теория формальных грамматик и автоматов; - student2.ru Теория формальных грамматик и автоматов; - student2.ru , т.е. каждая Теория формальных грамматик и автоматов; - student2.ru есть непосредственное следствие Теория формальных грамматик и автоматов; - student2.ru (n — длина вывода).

Язык грамматики — множество всех слов в алфавите V, выводимых из начального символа I.

Теория формальных грамматик и автоматов; - student2.ru ; Теория формальных грамматик и автоматов; - student2.ru

Грамматики G и G1, называются эквивалентными, если Теория формальных грамматик и автоматов; - student2.ru их языки совпадают.

Пример: грамматика нечетных чисел.

Теория формальных грамматик и автоматов; - student2.ru

Теория формальных грамматик и автоматов; - student2.ru — язык грамматики

Теория формальных грамматик и автоматов; - student2.ru

Теория формальных грамматик и автоматов; - student2.ru

Теория формальных грамматик и автоматов; - student2.ru

Теория формальных грамматик и автоматов; - student2.ru

Теория формальных грамматик и автоматов; - student2.ru

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

Автоматомназывается дискретный преобразователь информации, способный принимать различные состояния, переходить под воздействием входных сигналов из одного состояния в другое и выдавать выходные сигналы.

Если множество состояний автомата, а так же множества входных и выходных сигналов конечны, то автомат называется конечным автоматом.

Математической моделью реального конечного автомата является абстрактный автомат, который имеет один входной канал и один выходной канал.

Теория формальных грамматик и автоматов; - student2.ru Теория формальных грамматик и автоматов; - student2.ru

Q(q0,q1…qn)
X y(y1,y2,…,yk)

Автомат — последовательность (кортеж) из пяти элементов (Q,Σ,δ,S0,F), где:

  • Q — конечное множество состояний автомата – алфавит состояний
  • Σ — алфавит языка, который понимает автомат, (входной и выходной алфавит)
  • δ — функция перехода, такая что Теория формальных грамматик и автоматов; - student2.ru
  • S0 — начальное состояние, состояние когда автомат еще не прочитал ни одного символа
  • F — множество состояний, называемое «конечные состояния».

Можно утверждать, что язык L, который читается автоматом M, состоит из множества слов w на базе алфавита Σ, так что если эти слова вводятся в M, он приходит в одно из состояний F:

Теория формальных грамматик и автоматов; - student2.ru

отдельные символы, образующие алфавит – буквы, а любые упорядоченные последовательности букв данного алфавита – слова в этом алфавите.

Например. В алфавите X = (x1, x2), состоящем из двух букв, словами будут: x1, x2, x1x1, x1x2, x2x1,x2x2, x1x1x1, и т.д.

d - функция переходов, определяющая состояние автомата a(t+1), в котором автомат будет находиться в момент времени (t+1), в зависимости от состояния автомата a(t) и входного сигнала x(t) в момент времени t, т.е. a(t+1) = d [a(t),x(t)], l - функция выходов, определяющая значение выходного сигнала y(t) в зависимости от состояния автомата a(t) и входного сигнала x(t) в момент времени t, т.е. y(t) = l[a(t), x(t)].

Автомат функционирует в дискретные моменты времени, интервал между которыми Т называется тактом. При этом в каждый дискретный момент времени на вход автомата поступает одна буква входного алфавита, автомат переходит из одного состояния в другое и выдается одна буква выходного алфавита. В зависимости от того, как задается длительность такта Т, различают автоматы синхронного действия (T = const) и асинхронного действия (T ¹ const).

Детерминированный автомат– автомат каждой паре символов q(t) и x(t) ставит в однозначное соответствие пару символов q(t+1) и y(t).

Вероятностные или стохастические автоматы, в которых переход из одного состояния в другое под воздействием случайных или детерминированных входных сигналов происходит случайно. Работа таких автоматов описывается уже матрицей переходов d, элементами которой являются вероятности переходов из одного состояния в другое.

Применяемые на практике автоматы принято разделять на два класса: - это автоматы Мили и автоматы Мура.

Отличительной особенностью автоматов Мили является то, что их выходные сигналы зависят как от состояния автомата, так и от значения входного сигнала. В автоматах Мура выходные сигналы y(t) в каждый дискретный момент времени t однозначно определяются состоянием автомата в тот же момент времени и не зависят от значения входного сигнала.

Наши рекомендации