Мегаобучалка Главная | О нас | Обратная связь  


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




Поможем в ✍️ написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

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

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

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

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

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

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

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

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

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

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



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

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

.

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

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

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

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

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

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

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

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

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

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




Читайте также:
Как построить свою речь (словесное оформление): При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою...
Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы...



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (508)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.007 сек.)
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7