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


 

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

35980. Личность в системе межличностных отношений 40 KB
  Процесс обучения его сущность функции виды 2. Процесс обучения его сущность функции виды Дидактика это наука об обучении и образовании их целям содержании методах средствах и организационных формах. Дидактика это область педагогики исследующая закономерности процесса обучения. Предмет дидактики закономерности и принципы обучения его цели научные основы содержания образования методы формы средства.
35981. Мотивационная сфера личности. Содержание образования как фундамент культуры личности 40 KB
  Содержание образования как фундамент культуры личности Образова́ние целенаправленный процесс воспитания и обучения в интересах человека общества государства сопровождающийся достижения гражданином обучающимся установленных государством образовательных уровней Культура это предпосылка и результат образованности человека. Под содержанием образования следует понимать: 1 систему научных знаний практических умений и навыков; 2 систему мировоззренческих и нравственноэстетических идей которые необходимо приобрести учащимся в процессе...
35982. Принципы научной лексикографии и фразеологии. Словари РЯ 45 KB
  Словари РЯ. Лингвистические словари бывают одноязычными двуязычными и многоязычными. К числу одноязычных лингвистических словарей относятся: словари синонимов омонимов антонимов паронимов исторические этимологические диалектологические фразеологические словари иностранных слов нормативные и др. Различаются словари академического типа и словарисправочники.
35984. Этапы развития PR в США 44.5 KB
  Общепринято выделять два основных этапа развития PR в США до конца 19 века и 20 век. Начало 17 века 10е годы 19 века. 10е годы 19 века конец 19 века. Начало 20 века середина 40х годов 20 века.
35985. Абстрактный экспрессионизм 44.38 KB
  Портрет и мечта Portrit nd Drem 1953 Пасха и тотем Ester nd the Totem 1953 Серость океана Ocen Greyness 1953 Глубина The Deep Марк Ротко Эмиграция в США Глава семейства Ротковичей опасаясь того что детей заберут на службу в царскую армию решил эмигрировать в США следуя примеру многочисленных еврейских семей бежавших от погромов. В Америку уже уехали двое братьев Якова Ротковича которые обосновались в Портленде штат Орегон и занялись производством одежды. Раннее творчество...