Способы преобразования контекстно-свободной грамматик

КС называется не укорачиваемой или без пустых правил, если выполняются следующие условия:

1) Схема грамматики не содержит пустых правил;

2) Схема грамматики возможно содержит одно пустое правило , при этом не встречается в правой части никакого правила;

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

Правила построения:

1. Чтобы исключить e-правила в заданной грамматике для каждого не терминала , встречающемся в пустом правиле необходимо выполнить все возможные замены символа А пустыми цепочками в тех правилах грамматики, в которых А часто встречается в правой части;

2. Если существует правило и символ встречается в правой части какого-либо правила, то вводят дополнительный не терминал и правило .

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

, для каждого построим множество , для каждого сцепного правила поступаем аналогичным образом и получаем: , т.е. согласно построению, если из , то .

Магазинный автомат (МА): определение, понятие конфигурации МА. Определение функции переходов.

Головка магазинной ленты может перемещаться либо вверх, либо вниз, может оставаться неподвижной. Перемещение вверх всегда связано с записью символа в магазин, а вниз – считывание.

Магазинный автомат задается следующими множествами:

.

, где состояние МА, -цепочка символов, записанных в магазин.

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

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

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

- текущее состояние МА.

Пустому такту соответствует: .

Рассмотрим возможные случаи при переходе МА от одной конфигурации к другой.

1) Функция переходов определена, её значение известно, в этом случае новая конфигурация определяется значением функции переходов

2) Функция не определена, но определена функция задающая пустой такт, без чтения входной символа, в этом случае: ;

3) Функции и - не определены;