Способы преобразования контекстно-свободной грамматик
КС называется не укорачиваемой или без пустых правил, если выполняются следующие условия: 1) Схема грамматики не содержит пустых правил; 2) Схема грамматики возможно содержит одно пустое правило , при этом не встречается в правой части никакого правила; Для каждой КС грамматики можно построить эквивалентную ей не укорачивающуюся грамматику. Правила построения: 1. Чтобы исключить e-правила в заданной грамматике для каждого не терминала , встречающемся в пустом правиле необходимо выполнить все возможные замены символа А пустыми цепочками в тех правилах грамматики, в которых А часто встречается в правой части; 2. Если существует правило и символ встречается в правой части какого-либо правила, то вводят дополнительный не терминал и правило . Правило вида , где называется цепным. Для каждой КС, содержащей сцепные правила, можно построить эквивалентную ей грамматику без сцепных правил. , для каждого построим множество , для каждого сцепного правила поступаем аналогичным образом и получаем: , т.е. согласно построению, если из , то . Магазинный автомат (МА): определение, понятие конфигурации МА. Определение функции переходов. Головка магазинной ленты может перемещаться либо вверх, либо вниз, может оставаться неподвижной. Перемещение вверх всегда связано с записью символа в магазин, а вниз – считывание. Магазинный автомат задается следующими множествами: . , где состояние МА, -цепочка символов, записанных в магазин. Работу магазинного автомата можно представить в виде последовательности тактов, каждый такт работы связан с определением новой конфигурации, которая для магазинного автомата определяется следующим образом: -конфигурация магазинного автомата. необработанная часть входного слова, состоящая из символов входного алфавита, самый левый символ находится под входной головкой, если пустая – входная цепочка прочитана. - цепочка символов, находящихся в магазине, при этом самый правый символ находится в вершине магазина, если - пустая цепочка, значит магазин пуст. - текущее состояние МА. Пустому такту соответствует: . Рассмотрим возможные случаи при переходе МА от одной конфигурации к другой. 1) Функция переходов определена, её значение известно, в этом случае новая конфигурация определяется значением функции переходов 2) Функция не определена, но определена функция задающая пустой такт, без чтения входной символа, в этом случае: ; 3) Функции и - не определены;
Популярное: Почему стероиды повышают давление?: Основных причин три... Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (616)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |