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> * χ


 

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

36176. КОНСТРУКЦИЯ ДИСКА BD-ROM 50 KB
  Однако регистрирующий слой у BDдиска находится гораздо ближе к внешней поверхности той через которую осуществляется считывание чем у CD и DVD – на расстоянии всего 100 мкм от нее у CD это расстояние равно 11 мм у DVD – 06 мм. Если диск является двухслойным то второй информационный слой L1 располагается на расстоянии 25 мкм от первого слоя L0 ближе к внешней поверхности рис. Между этими двумя информационными слоями также находится разделительный слой поликарбоната. Диск BDROM Если диск является диском BDROM тиражированный...
36177. Digital Versatile Disc (DVD) 108.5 KB
  В процессе работы над новым носителем несколько раз менялось его название отражая основные намерения разработчиков на том или ином этапе: MMCD MultiMediCD; HDDVD High Density Digitl Video Disc; HDCD High Density CD. Даже названия у них были чемто схожи: SDDVD Super Density Digitl Video Disc перекликается с HDDVD. SDDVD тоже имеет двухслойную структуру однако она несколько иная чем у MMCD ибо образуется за счет того что склеиваются вместе две половинки диска каждая из которых имеет толщину 06 мм рис.
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амонесущие навесные Самонесущие – стены опирающиеся на фундамент и несущие нагрузку от собственного веса включая нагрузку от балконов эркеров парапетов и других элементов стены по всей высоте но не воспринимающие нагрузки от других частей здания. В соответствии со строительной системой каждый тип стены содержит несколько видов конструкций: бетонные стены из монолитного бетона крупных блоков или панелей; каменные стены ручной кладки стены из каменных блоков и панелей;...