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


 

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

16493. Подмосковная усадьба Кусково 37 KB
  Тема: Подмосковная усадьба Кусково В круг памятников архитектуры нельзя не ввести ряд подмосковных усадеб некогда располагавшихся близко от границ столицы а ныне вошедших в ее территорию. Среди них имеются как очень большие типа дворцовых рези
16494. Искусство Среднего царства 76 KB
  Искусство Среднего царства На время VIIX династии приходится первый Период распада страны. По свидетельству Манефона 70 царей VII династии правили 70 дней. Эта образная характеристика воссоздает перед нами картину смут которые наступили после деце
16495. Римское искусство 21.5 KB
  Римское искусство. Искусство древнего Рима как и древней Греции развивалось в рамках рабовладельческого общества поэтому именно эти два основных компонента имеют ввиду когда говорят об античном искусстве. Искусство Рима считают завершением художественного твор...
16496. КУРС ЛЕКЦИЙ ПО ИСТОРИИ РОССИИ 460 KB
  КУРС ЛЕКЦИЙ ПО ИСТОРИИ РОССИИ ВЛАДИМИРА ДМИТРИЕВИЧА ЮДИНА. Главное содержание курса повествование о том как из разрозненных славянских племён образовалась Русь и единый русский народ как образовалась империя и как она распалась. Задача курса изложить последов
16497. Лекции по истории Русской Церкви 902 KB
  ВВЕДЕНИЕ. ПОНЯТИЕ О НАУКЕ ИСТОРИЯ РУССКОЙ ЦЕРКВИ ЕЁ ПРЕДМЕТ И ЗАДАЧА. ИСТОЧНИКИ. ИСТОРИОГРАФИЯ. ЛИТЕРАТУРА. ПЕРИОДИЗАЦИЯ. Древний философ Плутарх писал что история есть учитель жизни. Ключевский В.О. писал: Хотя и говорят о том что история никого и ничему не на
16498. КУРС ЛЕКЦИЙ ПО ИСТОРИИ РОССИИ 216 KB
  Г КУРС ЛЕКЦИЙ ПО ИСТОРИИ РОССИИ ВЛАДИМИРА ДМИТРИЕВИЧА ЮДИНА. лавное содержание курса повествование о том как из разрозненных славянских племён образовалась Русь и единый русский народ как образовалась империя и как она распалась. Задача курса изложить после
16499. П.А. Столыпин. Политический портрет 126.5 KB
  РЕФЕРАТ П.А. Столыпин политический портрет Содержание Глава первая. Политическая и экономическая ситуация в России в конце 19 начало 20 века. стр. 2 ...
16500. Римское право. Учебное пособие 1.27 MB
  Московский государственный университет имени М.В Ломоносова Центр общественных наук И. Б. Новицкий РИМСКОЕ ПРАВО Ассоциация Гуманитарное знание ТЕИС Москва 2002 ББК67 Ответственный редактор проф. Е.А. Суханов Рекомендовано Ученым советом юридич...
16501. Регрессные обязательства между социалистическими хозяйственными организациями. Учебное пособие 1.01 MB
  Термин «регресс» (противоположный «прогрессу» — «движению вперед») по буквальному значению выражает «движение назад, обратно». Поэтому, например, выражение «регрессное требование» нередко заменяют, в качестве синонима, термином «обратное требование». Однако не всякое обратное требование подойдет под категорию регрессного требования, как ее понимают закон и арбитражно-судебная практика