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


 

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

38624. Технологии деятельности по решению проблем трудоустройства молодежи» (на примере Рязанской области) 650.5 KB
  Основные направления обеспечения занятости молодёжи в Российской Федерации. Анализ деятельности негосударственных субъектов занятости по обеспечению трудоустройства молодёжи в Рязанской области . В то же время учитывая что молодежь есть величайший стратегический и инновационный ресурс страны необходимо признать сферу ее занятости приоритетной частью социальноэкономической политики государства. Серьезной проблемой молодежной занятости является несоответствие объемов и профилей подготовки специалистов...
38625. Правовое регулирование гражданских правоотношений по оказанию юридических услуг 383.5 KB
  Общая характеристика возмездного оказания юридических услуг6 1. История становления и развития правоотношений по оказанию юридических услуг. Понятие юридической услуги в гражданском праве России . Правовое регулирование отношений по оказанию юридических услуг.
38626. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ ПО СОЦИАЛЬНОЙ ПСИХОЛОГИИ 127 KB
  В названии работы как правило представлены предмет и объект исследования. Важно четко знать предмет своего исследования какие психические явления изучаете. Экспериментальное и эмпирическое исследования – разные явления. СТРУКТУРА КУРСОВОЙ ДИПЛОМНОЙ РАБОТЫ Стандартная курсовая дипломная работа содержит: титульный лист; оглавление; введение 10 от общего объема; главы основной части: теоретическая 20 – 30 – заканчивается пронумерованными выводами; эмпирическая очень желательно чтобы по объему она была пропорциональна...
38627. ВЛИЯНИЕ НАНОРАЗМЕРНЫХ ДОБАВОК SI3N4 И НАНОВОЛОКОН УГЛЕРОДА НА СТРУКТУРУ И СВОЙСТВА ПОРОШКОВОЙ СТАЛИ У10П 13.14 MB
  Определение закономерностей спекания порошковых сталей содержащих наноразмерные добавки в исходной шихте Исходные данные Железный порошок марки ПЖВ 2. Физика спекания 3. Зависимость твердости порошковой стали с нанодобавками от времени и температуры спекания. Структура порошковых сталей в зависимости от содержания нанодобавок от времени и температуры спекания.
38628. Особенности социально-досуговой деятельности с молодежью (на примере Муниципального Бюджетного Учреждения Молодежного Центра «Успех» в п. Мостовском Краснодарского края) 23.2 MB
  Мостовском Краснодарского края Организация социальнодосуговой деятельности молодежи в Краснодарском крае. Однако это внешняя сторона характерная тем более не для всей молодежи в целом. Вопросам социальной работы с различными категориями молодого поколения посвящены многочисленные научные труды отечественных и зарубежных авторов в которых рассматриваются такие аспекты как история возникновения и развития актуальность содержание технологии и методы осуществления отдельных направлений социальной работы с...
38629. АВТОМАТИЗИРОВАННОЕ РАБОЧЕЕ МЕСТО СПЕЦИАЛИСТА ДЕКАНАТА 9.33 MB
  Некоторые организации используют для этого шкафы с папками но большинство предпочитают компьютеризированные способы базы данных позволяющие эффективно хранить структурировать и систематизировать большие объемы данных. И уже сегодня без баз данных невозможно представить работу большинства финансовых промышленных торговых и прочих организаций. Не будь баз данных они бы просто захлебнулись в информационной лавине. Базы данных позволяют хранить структурировать информацию и извлекать её оптимальным для пользователя образом.
38630. РОЗРОБЛЕННЯ ПРОЕКТУ СУПРОВОДУ СИСТЕМИ УПРАВЛІННЯ ДОРОЖНІМ ТРАФІКОМ НА БАЗІ ІНТЕЛЕКТУАЛЬНОЇ СИСТЕМИ ВІДЕОСПОСТЕРЕЖЕННЯ 2.75 MB
  Необхідно встановити систему інтелектуального відеоспостереження за найбільш завантаженими транспортом вулицями яка буде здатна самостійно фіксувати деякі порушення правил дорожнього руху таки як перевищення швидкості проїзд на червоне світло проїзд у забороненому напрямку виїзд на зустрічну смугу порушення дорожньої розмітки та інші і оформляти штрафи відповідно базі даних номерів автомобілів і систему штрафів Придністровської Молдавської Республіки а також мати можливість розпізнавання викрадених транспортних засобів. Планується...
38631. «Облачные» ресурсы 37.21 KB
  Одним из следствий процесса глобализации и интеграционных процессов стало появление «облачных» технологий, что позволяет пользователю не быть привязанным к географической точке и активизировать процесс обмена даже весьма большими объемами информации.
38632. МОДЕРНИЗАЦИЯ ТЕПЛОФИКАЦИОННОЙ УСТАНОВКИ ПАРОВОЙ ТУРБИНЫ Т-100-130 УРАЛЬСКОГО ТУРБИННОГО ЗАВОДА 277.5 KB
  Подогрев обратной сетевой воды производится в ПСГ1 и ПСГ2 . В зимнее время для подогрева воды можно использовать также встроенный в конденсатор выделенный пучок. При такой схеме подача циркуляционной воды в конденсатор сокращается и вакуум в нём ухудшается. Целью модернизации ТФУ является повышение термического КПД паровой турбины за счет увеличения температуры обратной сетевой воды на входе в ПСГ1 ПСГ2 что ведет к уменьшению расхода греющего пара в них и к уменьшению расхода топлива на его генерацию.