Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Основные понятия и определения. В этом разделе изложены некоторые аспекты теории формальных языков, существенные с точки зрения трансляции




Введение.

ЭЛЕМЕНТЫ ТЕОРИИ ФОРМАЛЬНЫХ ЯЗЫКОВ И ГРАММАТИК

В этом разделе изложены некоторые аспекты теории формальных языков, существенные с точки зрения трансляции. Здесь введены базовые понятия и даны определения, связанные с одним из основных механизмов определения языков - грамматиками, приведена наиболее распространенная классификация грамматик (по Хомскому). Особое внимание уделяется контекстно-свободным грамматикам и, в частности, их важному подклассу - регулярным грамматикам. Грамматики этих классов широко используются при трансляции языков программирования. Здесь не приводятся доказательства сформулированных фактов, свойств, теорем, доказательства правильности алгоритмов; их можно найти в книгах, указанных в списке литературы.

Определение: алфавит - это конечное множество символов.

Предполагается, что термин "символ" имеет достаточно ясный интуитивный смысл и не нуждается в дальнейшем уточнении.

 

Определение: цепочкой символов в алфавите V называется любая конечная последовательность символов этого алфавита.

 

Определение: цепочка, которая не содержит ни одного символа, называется пустой цепочкой. Для ее обозначения будем использовать символ e.

Более формально цепочка символов в алфавите V определяется следующим образом:

(1) e - цепочка в алфавите V;

(2) если a - цепочка в алфавите V и a - символ этого алфавита, то aa - цепочка в алфавите V;

(3) b - цепочка в алфавите V тогда и только тогда, когда она является таковой в силу (1) и (2).

 

Определение: если a и b - цепочки, то цепочка ab называется конкатенацией ( или сцеплением) цепочек a и b.

Например, если a = ab и b = cd, то ab = abcd.

Для любой цепочки a всегда ae = ea = a.

 

Определение: обращением ( или реверсом) цепочки a называется цепочка, символы которой записаны в обратном порядке.

Обращение цепочки a будем обозначать aR.

Например, если a = abcdef, то aR = fedcba.

Для пустой цепочки: e = eR.

 

Определение: n-ой степенью цепочки a (будем обозначать an) называется конкатенация n цепочек a.

a0 = e; an = aan-1 = an-1a.

 

Определение: длина цепочки - это число составляющих ее символов.

Например, если a = abcdefg, то длина a равна 7.

Длину цепочки a будем обозначать | a |. Длина e равна 0.

 

Определение: язык в алфавите V - это подмножество цепочек конечной длины в этом алфавите.

 

Определение: обозначим через V* множество, содержащее все цепочки в алфавите V, включая пустую цепочку e.

Например, если V={0,1}, то V* = {e, 0, 1, 00, 11, 01, 10, 000, 001, 011,...}.

 

Определение: обозначим через V+ множество, содержащее все цепочки в алфавите V, исключая пустую цепочку e.

Следовательно, V* = V+ È {e}.

Ясно, что каждый язык в алфавите V является подмножеством множества V*.

Известно несколько различных способов описания языков [3]. Один из них использует порождающие грамматики. Именно этот способ описания языков чаще всего будет использоваться нами в дальнейшем.

 

Определение: декартовым произведением A ´ B множеств A и B называется множество {(a,b) | a Î A, b Î B}.

 

Определение: порождающая грамматика G - это четверка (VT, VN, P, S), где

VT - алфавит терминальных символов (терминалов),

VN - алфавит нетерминальных символов (нетерминалов), не пересекающийся с VT,

P - конечное подмножество множества (VT È VN)+ ´ (VT È VN)*; элемент (a, b) множества P называется правилом вывода и записывается в виде a ® b,

S - начальный символ (цель) грамматики, S Î VN.

 

Для записи правил вывода с одинаковыми левыми частями

a ® b1 a ® b2... a ® bn

будем пользоваться сокращенной записью

a ® b1 | b2 |...| bn.

Каждое bi , i= 1, 2,...,n, будем называть альтернативой правила вывода из цепочки a.


 

Пример грамматики:

G1 = ({0,1}, {A,S}, P, S),

где P состоит из правил

S ® 0A1

0A ® 00A1

A ® e

 

Определение: цепочка b Î (VT È VN)* непосредственно выводима из цепочки a Î (VT È VN)+ в грамматике G = (VT, VN, P, S) (обозначим a ® b), если a = x1gx2, b = x1dx2, где x1, x2, d Î (VT È VN)*, g Î (VT È VN)+ и правило вывода g ® d содержится в P.

Например, цепочка 00A11 непосредственно выводима из 0A1 в грамматике G1.

 

Определение: цепочка b Î (VT È VN)* выводима из цепочки
a Î (VT È VN)+ в грамматике G = (VT, VN, P, S) (обозначим a Þ b), если существуют цепочки g0, g1,..., gn (n³0), такие, что a = g0 ® g1 ®... ® gn= b.

 

Определение: последовательность g0, g1,..., gn называется выводом длины n.

Например, S Þ 000A111 в грамматике G1 (см. пример выше), т.к. существует вывод S ® 0A1 ® 00A11 ® 000A111. Длина вывода равна 3.

 

Определение: языком, порождаемым грамматикой G = (VT, VN, P, S), называется множество L(G)={a Î VT* | S Þ a}.

Другими словами, L(G) - это все цепочки в алфавите VT, которые выводимы из S с помощью P.

Например, L(G1) = {0n1n | n>0}.

 

Определение: цепочка a Î (VT È VN)*, для которой S Þ a, называется сентенциальной формой в грамматике G = (VT, VN, P, S).

Таким образом, язык, порождаемый грамматикой, можно определить как множество терминальных сентенциальных форм.

 

Определение: грамматики G1 и G2 называются эквивалентными, если L(G1) = L(G2).

Например, G1 = ({0,1}, {A,S}, P1, S) и G2 = ({0,1}, {S}, P2, S), где

P1: S ® 0A1 P2: S ® 0S1 | 01

0A ® 00A1

A ® e

эквивалентны, т.к. обе порождают язык

L(G1) = L(G2) = {0n1n | n>0}.

 

Определение: грамматики G1 и G2 почти эквивалентны, если
L(G1) È {e} = L(G2) È {e}.

Другими словами, грамматики почти эквивалентны, если языки, ими порождаемые, отличаются не более, чем на e.

Например, G1 = ({0,1}, {A,S}, P1, S) и G2 = ({0,1}, {S}, P2, S), где

P1: S ® 0A1 P2: S ® 0S1 | e

0A ® 00A1

A ® e

почти эквивалентны, т.к. L(G1)={0n1n | n>0}, а L(G2)={0n1n | n³0}, т.е. L(G2) состоит из всех цепочек языка L(G1) и пустой цепочки, которая в L(G1) не входит.

Классификация грамматик и языков по Хомскому

(грамматики классифицируются по виду их правил вывода)

ТИП 0:

Грамматика G = (VT, VN, P, S) называется грамматикой типа 0, если на правила вывода не накладывается никаких ограничений (кроме тех, которые указаны в определении грамматики).

 

ТИП 1:

Грамматика G = (VT, VN, P, S) называется неукорачивающей грамматикой, если каждое правило из P имеет вид a ® b, где a Î (VT È VN)+, b Î (VT È VN)+ и | a | Ì | b |.

 

Грамматика G = (VT, VN, P, S) называется контекстно-зависимой (КЗ), если каждое правило из P имеет вид a ® b, где a = x1Ax2; b = x1gx2; A Î VN; g Î (VT È VN)+; x1,x2 Î (VT È VN)*.

 

Грамматику типа 1 можно определить как неукорачивающую либо как контекстно-зависимую.

Выбор определения не влияет на множество языков, порождаемых грамматиками этого класса, поскольку доказано, что множество языков, порождаемых неукорачивающими грамматиками, совпадает с множеством языков, порождаемых КЗ-грамматиками.

 

ТИП 2:

Грамматика G = (VT, VN, P, S) называется контекстно-свободной (КС), если каждое правило из Р имеет вид A ® b, где A Î VN, b Î (VT È VN)+.

 

Грамматика G = (VT, VN, P, S) называется укорачивающей контекстно-свободной (УКС), если каждое правило из Р имеет вид A ® b, где A Î VN, b Î (VT È VN)*.

 

Грамматику типа 2 можно определить как контекстно-свободную либо как укорачивающую контекстно-свободную.

Возможность выбора обусловлена тем, что для каждой УКС-грамматики существует почти эквивалентная КС-грамматика.


 

ТИП 3:

Грамматика G = (VT, VN, P, S) называется праволинейной, если каждое правило из Р имеет вид A ® tB либо A ® t, где A Î VN, B Î VN, t Î VT.

 

Грамматика G = (VT, VN, P, S) называется леволинейной, если каждое правило из Р имеет вид A ® Bt либо A ® t, где A Î VN, B Î VN, t Î VT.

 

Грамматику типа 3 (регулярную, Р-грамматику) можно определить как праволинейную либо как леволинейную.

Выбор определения не влияет на множество языков, порождаемых грамматиками этого класса, поскольку доказано, что множество языков, порождаемых праволинейными грамматиками, совпадает с множеством языков, порождаемых леволинейными грамматиками.

 

Соотношения между типами грамматик:

(1) любая регулярная грамматика является КС-грамматикой;

(2) любая регулярная грамматика является УКС-грамматикой;

(3) любая КС-грамматика является КЗ-грамматикой;

(4) любая КС-грамматика является неукорачивающей грамматикой;

(5) любая КЗ-грамматика является грамматикой типа 0.

(6) любая неукорачивающая грамматика является грамматикой типа 0.

Замечание: УКС-грамматика, содержащая правила вида A ® e, не является КЗ-грамматикой и не является неукорачивающей грамматикой.

 

Определение: язык L(G) является языком типа k, если его можно описать грамматикой типа k.

 

Соотношения между типами языков:

(1) каждый регулярный язык является КС-языком, но существуют КС-языки, которые не являются регулярными (например, L = {anbn | n>0}).

(2) каждый КС-язык является КЗ-языком, но существуют КЗ-языки, которые не являются КС-языками (например, L = {anbncn | n>0}).

(3) каждый КЗ-язык является языком типа 0.

Замечание: УКС-язык, содержащий пустую цепочку, не является КЗ-языком.

Замечание: следует подчеркнуть, что если язык задан грамматикой типа k, то это не значит, что не существует грамматики типа k’ (k’>k), описывающей тот же язык. Поэтому, когда говорят о языке типа k, обычно имеют в виду максимально возможный номер k.

 

Например, КЗ-грамматика G1 = ({0,1}, {A,S}, P1, S) и

КС-грамматика G2 = ({0,1}, {S}, P2, S), где

P1: S ® 0A1 P2: S ® 0S1 | 01

0A ® 00A1

A ® e

описывают один и тот же язык L = L(G1) = L(G2) = { 0n1n | n>0}. Язык L называют КС-языком, т.к. существует КС-грамматика, его описывающая. Но он не является регулярным языком,т.к. не существует регулярной грамматики, описывающей этот язык [3].




Поделиться с друзьями:


Дата добавления: 2015-06-27; Просмотров: 434; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.035 сек.