29370

Определение формальной грамматики

Доклад

Информатика, кибернетика и программирование

Конечное множество символов неделимых в данном рассмотрении в теории формальных грамматик называется словарем или алфавитом а символы входящие в множество буквами алфавита. Последовательность букв алфавита называется словом или цепочкой в этом алфавите. Если задан алфавит A то обозначим A множество всевозможных цепочек которые могут быть построены из букв алфавита A. Формальной порождающей грамматикой Г называется следующая совокупность четырех объектов: Г = { Vт VA I VA R } где Vт терминальный алфавит словарь; буквы этого...

Английский

2013-08-21

49 KB

2 чел.

3) Определение формальной грамматики.

Определение. Конечное множество символов, неделимых в данном рассмотрении, в теории формальных грамматик называется словарем, или алфавитом, а символы, входящие в множество, - буквами алфавита.

Например, алфавит A = {a, b, c, +, !} содержит 5 букв, а алфавит B = {00, 01, 10, 11} содержит 4 буквы, каждая из которых состоит из двух символов.

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

Например, слово в алфавите A a = ab++c имеет длину l(a) = 5, а слово в алфавите B b = 00110010 имеет длину l (b) = 4.

Если задан алфавит A, то обозначим A* множество всевозможных цепочек, которые могут быть построены из букв алфавита A. При этом предполагается, что пустая цепочка, которую обозначим знаком $, также входит в множество A*.

Определение. Формальной порождающей грамматикой Г называется следующая совокупность четырех объектов: Г = { Vт, VA, <I>  VA, R }, где

Vт - терминальный алфавит (словарь); буквы этого алфавита называются терминальными символами; из них строятся цепочки, порождаемые грамматикой;

VA - нетерминальный, вспомогательный алфавит (словарь); буквы этого алфавита (нетерминальные символы) используются при построении цепочек; они могут входить в промежуточные цепочки, но не должны входить в результат порождения;

<I> - начальный символ грамматики <I>  VA;

R - множество правил вывода, или порождающих правил вида α  β , где α и β - цепочки , построенные из букв алфавита Vт  VA, который называют полным алфавитом (словарем) грамматики Г.

В множество правил грамматики могут также входить правила с пустой правой частью вида <Е>  . Чтобы избежать неопределенности из-за отсутствия символа в правой части правила, условимся использовать символ пустой цепочки, записывая такое правило в виде <Е>  $.

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

Определение. Пусть r = τ → ϒ - правило грамматики Г и α = χ' τ χ" - цепочка символов, причем χ', χ"  (Vт  VA) *. Тогда цепочкα β = χ'  χ " может быть получена из цепочки α путем применения правила r (т.е. заменой в цепочке α τ на ). В этом случае говорят, что цепочка β непосредственно выведена из цепочки α и обозначают α  β.

Определение. Множество конечных цепочек терминального алфавита Vт грамматики Г, выводимых из начального символа <I>, называется языком, порождаемым грамматикой Г и обозначается L(Г).

L( Г ) = {   Vт* | <I> * }

Определение. Если язык, порождаемый грамматикой Г, не содержит ни одной конечной цепочки (конечного слова), то он называется пустым.

Утверждение. Для того, чтобы язык L(Г) не был пустым, в множестве R должно быть хотя бы одно правило вида r = χ  ψ, где ψ  Vт* и должен существовать вывод

<I> * χ


 

А также другие работы, которые могут Вас заинтересовать

36178. Налоги налогообложение 255.5 KB
  Принцип справедливости утверждающий всеобщность обложения и равномерность распределения налога между гражданами соразмерно их доходам которыми они пользуются под покровительством и защитой государства. Принцип экономии заключающийся в сокращении издержек взимания налога и рационализации системы налогообложения. Все последующие функциональные элементы налога объекты налогообложения ставки льготы и др. Расчет налога производится непосредственно от налоговой базы.
36179. Теория финансов 212 KB
  Страховая защита и страховые фонды Страхование создание специальными организациями фондов в денежной форме за счет страховых взносов юридических и физических лиц и предназначенных для реального возмещения только участникам их создания ущерба возникающего в результате наступления стихийных событий и несчастных случаев. страхование предусматривает перераспределение ущерба как в пространстве так и во времени; страховые взносы мобилизованные страховщиком имеют возвратный характер. Страхование подразделяется на три отрасли...
36180. Финансы организаций 210.5 KB
  Распределительная функция обеспечивает: образование целевых фондов денежных средств и поддержание рациональной структуры капитала; образование фонда возмещения который обеспечивает покрытие затрат на простое воспроизводство; формирование фонда оплаты труда возмещение затрат труда который состоит из двух частей: включаемой в затраты по производству и реализации продукции товаров работ услуг и образуемой за счет прибыли организации. Принцип самоокупаемости и самофинансирования означает полную окупаемость затрат на производство и...
36181. Финансовый менеджмент малого бизнеса 42.5 KB
  Основные этапы жизненного цикла малого предприятия; 1 этап разработка технологии и создание коммерческой схемы товара. В этот периодвыручка практически нулевая а денежные потоки предприятия отрицательные. Для этого необходимо определить посильные для предприятия темпыприроста оборота.
36182. Финансовый менеджмент. Учебное пособие 222.5 KB
  Потапова финансовый менеджмент Информационное обеспечение и финансовый анализ деятельности компании Учебнометодическое пособие Минск 2004 УДК 658. Информационное обеспечение и финансовый анализ деятельности компании: Учеб. Дается классификация финансовых коэффициентов характеризующих ликвидность деловую активность платежеспособность и рыночную активность компании. 2004 Частный институт управления и предпринимательства 2004 Информационное обеспечение и финансовый анализ деятельности компании Лекция I.
36183. Организация деятельность коммерческих банков 637 KB
  Банковская деятельность отличается достаточно жесткой правовой регламентацией банковских операций и постоянным обновлением законодательства по их проведению. Поэтому особое внимание в работе уделено происшедшим в последние годы изменениям в осуществлении операций, например, по предоставлению банковского кредита, в подходах при оценке и управлению банковскими рисками, расчетам нормативов безопасного функционирования.
36184. Конструкции и материалы самонесущих и навесных наружных стен 18.67 KB
  Помимо различных дифференциаций можно выделить 2 типа стен: cамонесущие навесные Самонесущие – стены опирающиеся на фундамент и несущие нагрузку от собственного веса включая нагрузку от балконов эркеров парапетов и других элементов стены по всей высоте но не воспринимающие нагрузки от других частей здания. В соответствии со строительной системой каждый тип стены содержит несколько видов конструкций: бетонные стены из монолитного бетона крупных блоков или панелей; каменные стены ручной кладки стены из каменных блоков и панелей;...
36185. Конструкции и материалы самонесущих и навесных наружных стен. Их особенности 16.22 KB
  Стена отделяет помещение от внешнего пространства наружные стены или от других помещений внутренние стены выполняя тем самым ограждающую функцию. Помимо различных дифференциаций можно выделить 2 типа стен: cамонесущие навесные Самонесущие – стены опирающиеся на фундамент и несущие нагрузку от собственного веса включая нагрузку от балконов эркеров парапетов и других элементов стены по всей высоте но не воспринимающие нагрузки от других частей здания. В соответствии со строительной системой каждый тип стены содержит несколько...
36186. Балконы, лоджии и эркеры 23.87 KB
  Устройство балконов лоджий и эркеров повышает комфортность жилых и общественных помещений и в то же время обогащает пластику фасадов зданий. Лоджии в отличие от балконов по боковым сторонам ограждены стенами и могут быть как встроенными в объем здания так и выносными. ОГРАЖДЕНИЯ БАЛКОНОВ Могут выполняться из различных материалов: непрозрачного стекла пластиков древесных материалов волнистой листовой стали на каркасе и т. КОНСТРУКТИВНЫЕ РЕШЕНИЯ Конструктивное решение балконов зависит от схемы опирания балконной плиты консольное...