АВТОМАТНЫЕ ГРАММАТИКИ И ЯЗЫКИ Класс 3: автоматные грамматики (А-грамматики). Вид порождающих правил: A aB или A a где A, В – не терминалы, a – терминал. Пример автоматной грамматики Грамматика: G 4 (L) = {, N, S, P} = {a, b}, N = {S, T, C}, S = {S}, P = {S aT, T aT, T bC, C bC, C a}. Процесс порождения: S => aT => abC => aba, S => aT => aaT => aabC => aabbC => aabba,... 1) на каждом шаге цепочка увеличивается на один терминальный символ (в конце перед нетерминалом); 2) на всех шагах, кроме последнего, цепочка содержит вначале терминальные символы, а в конце – один нетерминал.

РАСПОЗНАВАТЕЛЬ АВТОМАТНОЙ ГРАММАТИКИ – КОНЕЧНЫЙ АВТОМАТ Конечный автомат – это частный вид машины Тьюринга, в которой: 1) лента является входной, с нее считываются символы, но ничего не пишется; 2) на каждом шаге работы автомата считывается очередной символ, лента движется влево, устройство управления делает переход в новое состояние в соответствии с подходящим правилом перехода Начало работы: считывающая головка автомата обозревает самый левый символ на ленте; автомат находится в начальном состоянии. Если в конце работы головка автомата обозревает символ, расположенный следом за самым правым символом на ленте, и автомат находится в заключительном состоянии, то говорят, что входная цепочка успешно распознана (допущена) автоматом. В противном случае - цепочка не допущена.

КОНЕЧНЫЙ АВТОМАТ: РЕАЛИЗАЦИЯ 1. Справа после цепочки входных символов на ленте автомата – «пустая» клетка, пусть это будет символ « ». 2. Каждому не терминалу грамматики соответствует одно состояние конечного автомата. 3. В грамматике добавим еще один нетерминал Z, которому соответствует заключительное состояние. Нетерминал Z добавляется в правые части правил вида: A a. Такое правило будет в виде: A aZ 4. Успешному распознаванию в работе конечного автомата соответствует следующая ситуация: головка автомата обозревает символ « »; автомат находится в заключительном состоянии. Тогда входная цепочка допущена автоматом.

ПРИМЕР КОНЕЧНОГО АВТОМАТА Грамматика: G 4 (L) = {, N, S, P} = {a, b}, N = {S, T, C}, S = {S}, P = {S aT, T aT, T bC, C bC, C aZ}. Автомат в виде таблицы: Примеры: a a a b b a a b a b a a S T T T C C Z S T C S T C Z Входной символ_ Состояние ab ST TTC CZC Zдопуск

РЕАЛИЗАЦИЯ ДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА Входная цепочка: массив C, Номер текущего символа: i, Состояние s: 1, 2,..., k, k+1. Начальное: 1, заключительное: k, ошибочное: k+1. Матрица переходов: массив M. Таблица перекодировки (символ -> номер столбца): T. i:=1; s:=1; while s<k do begin {i <= длины строки С} j:=T[ord(C[i])]; s:=M[s,j]; i:=i+1 end; if (s=k)and(C[i]= ) then «допуск» else «нет» Трудоемкость: O(n)

НЕДЕТЕРМИНИРОВАННЫЙ КОНЕЧНЫЙ АВТОМАТ Грамматика: G 5 (L) = {, N, S, P} = {a, b}, N = {S, T, C}, S = {S}, P = {S aT, S aC, T aT, T aC, T bC, C bC, C b}. Замена C b на C bZ. Недетерминированности: {S aT, S aC}, {T aT, T aC}, {C bC, C bZ} Примеры: a a b b S T/C T/C C/Z C/Z Входной символ_ Состояние ab ST/C T C CC/Z Z допуск

РЕАЛИЗАЦИЯ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА Входная цепочка: массив C, Номер текущего символа: i, Состояние s: битовый вектор длиной k бит. Начальное: (1,0,0,... 0) заключительное: (?, ?, ?,..., ?, 1) ошибочное: (0,0,0,... 0) Матрица переходов: массив M из битовых векторов длиной k. Таблица перекодировки (символ -> номер столбца): T. i:=1; s:= (1,0,0,... 0) ; while (s<> (0,0,0,... 0) )and(C[i]<> ) do {i<= длины строки С} begin j:=T[ord(C[i])]; s1:= (0,0,0,... 0) ; for p:=1 to k do if s[p]=1 then s1:=s1 or M[p,j]; s:=s1; i:=i+1 end; if (s[k]=1)and(C[i]= ) then «допуск» else «нет» Трудоемкость: O(k 2 n)

ПРЕОБРАЗОВАНИЕ НЕДЕТЕРМИНИРОВАННОЙ АВТОМАТНОЙ ГРАММАТИКИ К ДЕТЕРМИНИРОВАННОЙ Пусть в грамматике (с добавленным нетерминалом Z) есть недетерминированностьть: {A bB 1, A bB 2,..., A bB n }. (*) Обозначим: B*={B 1, B 2,..., B n }. Вместо порождающих правил (*) добавим правило: A bB* В дополнение к правилам {B 1β 1, B 2β 2,..., B nβ n } добавим правила: {B*β 1, B*β 2,..., B*β n }. Преобразованная грамматика будет порождать в точности то же самое множество цепочек, что и исходная грамматика, т.е. язык не изменится. Применим такое же преобразование ко всем другим недетерминированность- там, в результате грамматика станет детерминированной. Общее количество имевшихся в исходной грамматике не терминалов и вновь добавленных не более чем 2 k, где k – количество имевшихся в исходной грамматике не терминалов. ____________________________________________________________________________________________________________________________________ Теорема: любую недетерминированную автоматную грамматику можно преобразовать к эквивалентной детерминированной. Следствие: Все автоматные языки детерминированные.

Пример преобразования Грамматика: G 5 (L) = {, N, S, P} = {a, b}, N = {S, T, C}, S = {S}, P = {S aT, S aC, T aT, T aC, T bC, C bC, C bZ}. Недетерминированности: {S aT, S aC}, D = {T, C} {T aT, T aC}, то же самое, {C bC, C bZ}, E = {C, Z}. Здесь E – заключительный нетерминал. Преобразованные правила: {S aD, D aD, D bE, T aD, T bC, C bE, E bE} Преобразованная грамматика без лишних правил: {S aD, D aD, D bE, E bE} Преобразованная грамматика без заключительного не терминала: {S aD, D aD, D bE, E bE, D b, E b} ________________________________________________________________________________________________________________________________________ 1. Если заключительный нетерминал W не встречается в левой части ни одного из правил, то он удаляется из всех правых частей. 2. Если заключительный нетерминал W имеется в левой части хотя бы одного из правил, то для каждого из правил вида: U dW добавляется правило: U d.

После преобразования в грамматике могут появиться бесполезные порождающие правила и бесполезные не терминалы. Они не влияют на процесс порождения (и, соответственно, на процесс распознавания), поэтому их можно удалить, не изменяя сам язык. Алгоритм 1. Обнаружение бесполезных не терминалов 1 типа (таких, которые не могут быть порождены, начиная с начального не терминала). 1. Начальный нетерминал помечается как «полезный». 2. Просматриваются все порождающие правила, у которых в левой части имеются не терминалы, помеченные как «полезные». Нетерминалы в правых частях таких правил также помечаются как «полезные» й шаг повторяется до тех пор, пока не останется непросмотренных правил. 4. Нетерминалы, не помеченные как «полезные», считаются бесполезными. После завершения алгоритма 1 из грамматики необходимо удалить все бесполезные не терминалы и все порождающие правила, где встречаются эти не терминалы (как в левой, так и в правой части).

Алгоритм 2. Обнаружение бесполезных не терминалов 2 типа (таких, из которых не может быть порождена терминальная цепочка). 1. Просматриваются все порождающие правила, у которых в правой части имеются только терминалы. Нетерминалы в левых частях таких правил помечаются как «полезные». 2. Просматриваются все порождающие правила, у которых в правой части имеются не терминалы, помеченные как «полезные». Нетерминалы в левых частях таких правил также помечаются как «полезные» й шаг повторяется до тех пор, пока не останется непросмотренных правил. 4. Нетерминалы, не помеченные как «полезные», считаются бесполезными. После завершения алгоритма 2 из грамматики необходимо удалить все бесполезные не терминалы и все порождающие правила, где встречаются эти не терминалы (как в левой, так и в правой части).