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


 

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

13856. Профессиональная учительская этика в романе Белл Кауфман «Вверх по лестнице, ведущей вниз» 52.5 KB
  Роман Белл Кауфман Вверх по лестнице ведущей вниз опубликованный в 1960х годах заслужил признание не только в США роман обрел известность стал популярным без преувеличения во всем мире. Действие романа происходит в школе им. Кальвина Куллинджа в НьюЙорке. Главный г
13857. «Белая гвардия» Булгаков. Эссе 43 KB
  Вадим Матвеев Белая гвардия Булгаков. Эссе. Роман Булгакова наполнен историческими событиями от начала и до конца. 1918 год. Украина объявила независимость провозгласив гетмана в связи с чем обострились националистические настроения и рядовые украинцы сразу ра
13858. Джордж Оруэлл «1984» 32.58 KB
  Мосогутова Евгения Политология 4 курс Джордж Оруэлл 1984 Роман антиутопия Оруэлла1984 отражает настроения царившие в ХХ веке. Автор берет за основу реалии современного ему мира и возводит их в гроте
13859. Эссе Анализ романа Шодерло де Лакло «Опасные связи» 55.5 KB
  Эссе Анализ романа Шодерло де Лакло Опасные связи. Опасные связи единственный роман генерала Шодерло де Лакло основанный по утверждению автора на реальных событиях. Роман эпистолярного жанра что должно убедить читателя в подлинности излагаемого повествовани...
13860. Креативный анализ фильма « Последний урок» 24.46 KB
  Петрова Регина Креативный анализ фильма Последний урок Политическая целесообразность В основе сюжета фильма лежит история учительницы которая работает во французской школе для трудных подростков. Основная часть учеников это иммигранты из арабских стран...
13861. Анализ фильма «Конформист» 46 KB
  Ромазанов Д.М. Политология 4 курс. Анализ фильма Конформист Фильм Конформист режиссера Бернардо Бертолуччи снят в 1970 году по роману Альберто Моравиа. Главный герой Марчелло Клеричи интеллектуал о чем можно судить из его диалого
13862. Мультфильм «Персеполис» 41 KB
  абиров Д.Р. Задание по курсу Политическая этика Мультфильм Персеполис Персеполис французский полнометражный анимационный фильм режиссёра Маржана Сатрапии французской писательницы иранского происхождения. Сюжет в кратце: Бойкая Марьян восьми л
13863. Анализ фильма «Молитвы за Бобби» с точки зрения этики и морали 27.34 KB
  Анализ фильма Молитвы за Бобби с точки зрения этики и морали. Место действия. Действия фильма разворачивается в небольшом городе Walnut Creek в Соединенных Штатах Америки штат Калифорния 60 тысяч населения. Город представляет собой американскую мечту с красивыми уло...
13864. Эссе по политической этике на тему «Мораль в произведении Уильяма Голдинга «Повелитель мух» 28.98 KB
  Эссе по политической этике на тему Мораль в произведении Уильяма Голдинга Повелитель мух Имя Уильяма Голдинга отчего то не столь популярно в мире. Подразумеваю что редко можно встретить его в одном ряду например с Хемингуэем Маркесом Ремарком Фицджеральдом