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


 

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

4370. PHP циклы и функции пользователя 93 KB
  PHP Циклы В РНР реализованы два типа циклов: while и for. Цикл while бывает двух типов Проверяющий условие перед проходом цикла while (условие) блок операторов Проверяющий условие после прохода цикла do блок операторов while ус...
4371. Создание динамических сайтов средствами PHP и MySQL 80.5 KB
  PHP и MySQL. Основным достоинством динамических сайтов, по сравнению со статическими, является возможность отделения данных от кода, отвечающего за их визуальное представление. Благодаря такому подходу, можно создавать сайты, формирующие страницы в...
4372. Программирование на языках высокого уровня, лабораторный практикум 305.5 KB
  Программирование на языках высокого уровня, включающей алгоритмизацию задач и изучение подмножества языка Си в средах программирования Borland C++ и Microsoft Visual C++, а также в приобретении практических навыков работы с персональным компьютером.
4373. Управление памятью на уровне пользователя 129.5 KB
  Управление памятью на уровне пользователя На этапе постановки задачи программист должен решить, какую программу он должен создать, что и какими данными она должна оперировать. То есть возникает вопрос о количественной оценке используемых данных. Есл...
4374. Знакомство со средой разработки Borland C++3.1. Создание и отладка простых консольных приложений на языке Си. 42.51 KB
  Знакомство со средой разработки BorlandC++ Создание и отладка простых консольных приложений на языке Си. Напишите программу, запрашивающую у пользователя фамилию, имя и отчества(например: Whatisyourname?, или ...
4375. Введение в программирование на языке Си 33.45 KB
  Введение Добро пожаловать в мир языка программирования Си, который за время своего существования – порядка 40 лет – уже успел стать классическим, однако его актуальность несомненна и по сей день. Язык Си популярен как среди профессионалов...
4376. Основы языка Си и элементы C++ 326.96 KB
  Основы языка Си и элементы C++ Создание проекта в Microsoft Visual Studio Для разработки программ в среде Microsoft Visual Studio и Microsoft Visual Studio Express следует создать так называемый проект или решение....
4377. Операции и выражения в программировании 88.34 KB
  Операции и выражения Операторы В данной теме мы зададимся вопросом: Из чего состоят программы Если посмотреть на программный код, то в нем можно увидеть различные слова, знаки, цифры. Каждый из этих элементов несет вполне конкретную смысловую наг...
4378. Основы языка Java 1.36 MB
  Основы языка Java Задание Установка Java Runtime Environment и интегрированной среды разработки Eclipse. Введите jre в поисковой системе и выберите первую сверху ссылку. Выберите Download JRE. Примите лицензионное соглашение и выбери...