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


 

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

14418. Есть такая профессия - защищать Родину 482.72 KB
  Сочинение на тему: Есть такая профессия защищать Родину Я счастливый человек Я живу со своими родителями хожу в любимую школу слышу смех бабули и дедушки. Мне интересно читать книги рассматривать картинки в энциклопедиях изучать географические карты. Как мног
14419. Важный выбор 13.85 KB
  Важный выбор Мой важный выбор состоял в том что я решил сильно поменять свою жизнь поступив в суворовское военное училище. Одним летним утром я как обычно проснулся поздно но по новостям увидел передачу об Уссурийском суворовском военном училище.
14420. Важный выбор профессии 17.36 KB
  Я учусь в 8 классе мне 14 лет. Через несколько лет меня ждет расставание со школой. Но самое главное мне предстоит сделать очень важный выбор от которого впоследствии будет зависеть моя будущая жизнь. Кто поможет мне ответить на вопрос: Кем быть Куда пойти учиться ...
14421. Моя мечта 32 KB
  Среди десятков, сотен, тысяч принимаемых человеком решений ни одно не может сравниться по своему значению, по роли и влиянию на судьбу с решением выбора профессии.
14422. ТЕПЛОВЫЕ ЭЛЕКТРИЧЕСКИЕ СТАНЦИИ ДИПЛОМНОЕ ПРОЕКТИРОВАНИЕ 873.5 KB
  И.Б. Бакытжанов В.О. Байбекова ТЕПЛОВЫЕ ЭЛЕКТРИЧЕСКИЕ СТАНЦИИ ДИПЛОМНОЕ ПРОЕКТИРОВАНИЕ В учебном пособии рассмотрены вопрос выбора основного и вспомогательного оборудования ТЭС в соответствии с нормами технологического проектирования тепловых электрических с
14423. ОРГАНИЗАЦИЯ ГРУЗОВЫХ АВТОМОБИЛЬНЫХ ПЕРЕВОЗОК 327.39 KB
  ОРГАНИЗАЦИЯ ГРУЗОВЫХ АВТОМОБИЛЬНЫХ ПЕРЕВОЗОК Методическое пособие к курсовой работе по дисциплине Организация автомобильных перевозок и безопасность движения специальность 190601 Автомобили и автомобильное хозяйство ОБЩИЕ ПОЛОЖЕНИЯ Цель курсов...
14424. Изучение технологии производства тепло- и электроэнергии на ТЭЦ 413 KB
  Отчет по производственной практике Содержание Введение 1 Принципиальная технологическая упрощенная схема станции 2 Назначение основных элементов технологической схемы: склад топлива и система топливоподачи система топливоприготовления котельный агрегат ...
14425. Семей қаласындағы ЖЭО-3 салу мен оны пайдаланудың бизнес жоспары 166.5 KB
  Семей қаласындағы ЖЭО3 салу мен оны пайдаланудың бизнес жоспары Есептеу үшін бастапқы берілгендер ретінде электр және жылу энергияларының жылдық өндіру көлемдері және 1 кВтсағ электр энергиясы мен 1 Гкал жылу энергиясын өндіруге жұмсалатын шартты отынның меншікті ...