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


 

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

32243. Объемно-блочное строительство 117.5 KB
  Монолитная и сборномонолитная строительные системы применяются преимущественно для возведения зданий повышенной этажности. Первые примеры возведения многоэтажных гражданских зданий с монолитными бетонными стенами и перекрытиями в нашей стране относятся к 80м гг. осваивали технологию возведения таких зданий то с середины 80х они составили интенсивно развивающуюся отрасль городского жилищного строительства. На архитектурнопланировочное и конструктивное решение монолитных и сборномонолитных зданий существенно влияет применяемый метод...
32245. Метод подъема этажей 243 KB
  Идея строительства многоэтажных зданий методом подъема готовых перекрытий впервые была высказана французским инженером Лафаргом однако в его время она не могла быть осуществлена изза отсутствия необходимого подъемного оборудования. в США было построено методом подъема перекрытий первое многоэтажное здание. Вскоре после проведения эксперимента по подъему перекрытий этот метод получил широкое распространение и стал применяться во многих странах Европы и Японии.
32247. Разборно-переставная опалубка состоит из отдельных элементов (щитов, коробов, элементов креплений и т. д.), которые собираются для возведения железобетонного сооружения или части его в каждом отдельном случае 27 KB
  Устойчивость щитов опалубки обеспечивается подкосами которые устанавливаются через каждые 3 4 м. Для установки верхнего яруса короба опалубки нижние доски удлиненных щитов делают несколько длиннее и опирают их на щиты опалубки нижнего яруса башмака. В верхней части опалубки делаются вырезы для примыкания прогонов или прогонов и балок. Внизу одного из щитов короба делают отверстие для прочистки опалубки от мусора перед бетонированием.
32248. Скользящая опалубка 47.5 KB
  Основными элементами скользящей опалубки являются щиты домкратные рамы рабочий пол подвесные подмости домкратные стержни устанавливаемые по оси стен домкраты.Домкратные рамы являются основными несущими элементами на них устанавливают щиты опалубки которые воспринимают давление бетонной смеси. На домкратные рамы устанавливают домкраты которые опираясь на стержни поднимают всю конструкцию опалубки. Щиты опалубки устанавливают так чтобы расстояние между ними увеличивалось книзу образуя конусность в пределах высоты щитов или 5 7 мм на...
32249. Подъемно-переставная опалубка 21 KB
  Наружные и внутренние шиты опалубки закрепляют на подъемной головке которая устанавливается и поднимается по шахтоподъемнику. На подъемной головке закрепляют также рабочую площадку подвесные леса бункера для бетонной смеси лебедку лифтов и тепляк с юбкой тепляка. Щиты соседних ярусов закрепляют с помощью поперечных накладок.
32250. Объемно-переставная опалубка 49 KB
  Опалубка состоит из пространственных секций Побразной формы которые при соединении образуют туннели опалубки на квартиру или во всю ширину здания. Секции опалубки имеют переменную ширину в зависимости от принятого шага стен и различную длину. Бетонную смесь укладывают между туннелями опалубки для образования стен и на секции при бетонировании перекрытий. При демонтаже секции опалубки как бы сжимаются для чего сдвигают внутрь забетонированного туннеля боковые щиты опалубки щиты стен перемещают вниз горизонтальный щит перекрытий.
32251. Катучая опалубка 28.5 KB
  Каждый блок катучей опалубки состоит из нескольких металлических рам смонтированных на тележках передвигаемых на рельсах. Внешний контур металлических ферм и опалубки должен строго соответствовать очертанию бетонируемых конструкций.Применение подъемнокатучей опалубки снижает стоимость железобетонных работ по устройству покрытия здания на 20.Использование катучей опалубки прямоугольного сечения вдвое ускорило производство работ и позволило снизить трудоемкость 1 м3 железобетонных работ на 046 чел.