Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Общий вид цепочек А-языков и КС-языков



 

Мы хотим получить характеристику цепочек А-языков, которая будет полезна для доказательства того, что некоторые языки не являются автоматными. Следующую теорему об общем виде цепочек А-языков называют теоремой о “разрастании”, потому что она в сущности говорит о том, что если дан А-язык и достаточно длинная цепочка в нем, то в этой цепочке можно найти непустую подцепочку, которую можно повторить сколько угодно раз (т.е. она “разрастается”), и все полученные таким образом “новые” цепочки будут принадлежать тому же А-языку. С помощью этой теоремы часто приводят к противоречию предположение о том, что некоторый язык является автоматным.

Теорема 5.1. Пусть L - А-язык. Существует такая константа p, что если y Î L и ½y½³ p , то цепочку y можно записать в виде abg , где 0 <½b½£ p и ab ig Î L , для всех i ³ 0 .

Доказательство. Если L - конечный язык, то положим константу p больше длины самой длинной цепочки языка L, тогда ни одна из цепочек языка не удовлетворяет условиям теоремы и она верна. В противном случае, пусть M = (Q, S, d, q0, F) - конечный автомат с n состояниями и L(M) = L. Пусть p = n. Если y Î L и ½y½³ n, рассмотрим последовательность конфигураций, которую проходит автомат M, допуская цепочку y. Так как в этой последовательности, по крайней мере, n+1 конфигурация, то найдутся две конфигурации с одинаковыми состояниями. Поэтому, должна быть такая последовательность тактов, что (q 0, abg ) ú¾* (q 1, bg ) ú¾k (q 1, g ) ú¾* (q 2, e ) , для некоторого q 1 и 0 < k £ n. Отсюда 0 <½b½£ n.

Но тогда, для любого i > 0 автомат может проделать следующую последовательность тактов:

 

(q 0, ab i g ) ú¾* (q 1, b i g )

(q 1, b i g ) ú¾+ (q 1, b i-1 g)

..............

(q 1, b 2 g ) ú¾+ (q 1, bg)

(q 1, bg ) ú¾+ (q 1, g)

(q 1, g) ú¾* (q 2, e ) .

Для случая i = 0 все еще очевиднее: (q 0, ag ) ú¾* (q 1, g) ú¾* (q 2, e )

Так как abg Î L, то и ab i g Î L, для всех i ³ 0. š

Эта теорема обычно используется для доказательства того, что некоторые выбранные цепочки не являются цепочками А-языка и, следовательно, не могут быть определены А-грамматиками.

Следствие 5.1. Язык L, состоящий из цепочек x n y n не является автоматным языком.

Допустим, что он автоматный. Тогда, для достаточно большого n цепочка x n y n может быть представлена в виде abg, причем b ¹ e и ab i g Î L, для всех i ³ 0.

Если b = x...x или b = y...y, то ag = ab 0 g Ï L, так как количество символов x и y в цепочке ag различно. Если b = x...xy...y, то abbg = ab 2g Ï L, так как в цепочке abbg символы x и y будут перемешаны. Полученное противоречие доказывает, что L - не является А-языком. š

Следствие 5.2.Язык арифметических выражений не является А-языком, так как он может содержать произвольное количество вложенных скобок, причем количество открывающих скобок совпадает с количеством закрывающих. Аналогично не является А-языком любой язык, содержащий вложенные конструкции типа фигурных скобок в языке C, begin - end, repeat - until и т.п. Каждая конечная А-грамматика, порождающая подобные конструкции, будет выводить и цепочки с неравным количеством открывающих и закрывающих скобок. Тем не менее анализировать подобные цепочки можно и с помощью автоматного подхода. При этом в синтаксисе языка допускается произвольное количество открывающих и закрывающих скобок, а контроль их парности возлагается на семантические подпрограммы. š

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

Теорема 5.2. Для любой КС-грамматики, которая не допускает вывода вида А Þ+ aАb, где ½a½> 0 и ½b½> 0 можно построить эквивалентную А-грамматику. š

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

Теорема 5.3. Для любого КС-языка L существует постоянная p такая, что если y Î L и ½y½ > p, то y = abgjl , где b¹e , j¹e и ab igj il Î L для любого i³0.

Доказательство. Аналогично с теоремой 5.1 рассмотрим только случай бесконечных языков.

Рассмотрим в бесконечном КС-языке L бесповторные деревья вывода, то есть такие, у которых ни на одной ветви нет повторяющихся нетерминалов. Таких деревьев конечное число. Максимальная высота бесповторного дерева v - равна количеству нетерминалов грамматики. Если максимальная длина правых частей правил грамматики равна b, то максимальная длина цепочки, выводимой бесповторными деревьями, будет не более bv. Положим p = bv. Рассмотрим цепочку с длиной больше p и ту ветвь ее дерева вывода, в которой нетерминалы повторяются.

Рассмотрим поддеревья D1 и D2 , начинающиеся с повторяющегося нетерминала A. Если D1 заменить на D2 , то получим дерево вывода цепочки agl. Подвеска дерева D2 к корню D1 возможна, так как после нее корень дерева D1 соответствует применению того же правила, что и корень дерева D2 . Таким образом, полученное дерево вывода является деревом вывода в той же грамматике.

Если D2 заменить на D1 , то получим дерево вывода цепочки ab 2gj 2l . Дерево D1 , которым заменяется D2 содержит в себе D2 в качестве поддерева. Заменив его на D1 , получим дерево вывода цепочки ab 3gj 3l . Продолжая такие замены, можно получить любую из цепочек ab igj il . š

Пример 5.1. Пусть дана КС-грамматика с правилами:

 

S ® aAp

A ® cAc½cbAb½d

 

Максимальная высота бесповторного дерева здесь равна 2, а максимальная длина цепочки, выводимая бесповторным деревом, равна 3 (бесповторно выводится только цепочка adp). На рис. 5.1 (а) показано дерево вывода цепочки acbdbp. Здесь принято следующее: a = a, b = cb, g = d, j = b, l = p. На рис. 5.1 (б) показана замена поддерева D1 на D2 , а на рис. 5.1 (в) замена D2 на D1 . †

Теорема 5.3, как и теорема 5.1, чаще всего используется для доказательства того, что некоторые цепочки не принадлежат КС-языкам.

Следствие 5.3. Язык L, состоящий из цепочек x ny nz n, не является КС-языком.

Действительно, разделяя эту цепочку на пять частей abgjl любым возможным способом, мы увидим, что либо agl Ï L из-за неравного количества символов x, y и z; либо ab 2gj 2l Ï L из-за перемешивания символов внутри цепочки.

 

Следствие 5.4. Языки программирования в общем случае не являются КС-языками.

Например, в языках программирования каждая конкретная процедура имеет одно и то же число аргументов в каждом месте, где она упоминается. Можно показать, что такой язык не контекстно-свободен, отобразив множество программ с тремя вызовами одной и той же процедуры на не КС-язык {0 n 10 n 10 n | n³0}.

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

Однако на практике все языки программирования считаются КС-языками. В компиляторах идентификаторы обычно обрабатываются лексическим анализатором и свертываются в лексемы прежде, чем достигают синтаксического анализатора. Контроль за их описанием до использования, также как и подсчет числа параметров в процедуре и т.п., возлагается на семантические подпрограммы, не входящие в собственно синтаксический анализ. Это позволяет существенно упростить синтаксис языков программирования.

 

Операции над языками

 

По определению язык - это множество цепочек, следовательно, над языками можно выполнять операции, правомерные как для множеств, так и для цепочек (строк символов). Определим некоторые из них.

Язык L называется объединением языков L1 и L2 (L= L1 È L2), если он содержит все цепочки из L1 вместе со всеми цепочками из L2 . Формально L = {a½a Î L1 или a Î L2}.

Язык L называется пересечением языков L1 и L2 (L= L1 Ç L2), если он содержит все цепочки, принадлежащие как L1, так и L2 . Формально L={a½a Î L1 и a Î L2}.

Язык L называется разностью языков L1 и L2 (L= L1 \ L2), если он содержит все цепочки из L1, которые не принадлежат L2 . Формально L={a½aÎL1 и aÏL2}.

Язык L называется дополнением языка L1 ( ), если он содержит все цепочки из некоторого универсального языка L2, которые не принадлежат L1 . Формально L={a½a Ï L1}.

Язык L называется конкатенацией (сцеплением) языков L1 и L2 (L= L1 L2), если он содержит попарные конкатенации всех возможных цепочек из L1 и L2 . Формально L={ab½a Î L1 и b Î L2}.

Итерация языка L, обозначаемая L*, определяется следующим образом:

(1) L0 = { e },

(2) Ln = LLn-1 для n ³ 0

(3) L*= Ln.

Позитивная итерация языка L, обозначаемая через L+, - это язык Ln. Заметим, что L+ = LL* = L*L и L* = L+ È { e }.

Язык L называется подстановкой языка L2 в язык L1 вместо терминала a (L= ), если он содержит все цепочки языка L1 , в которых терминал a заменен на все возможные цепочки языка L2.

Обращение языка L, обозначаемое LR, - это язык, содержащий все обращенные цепочки исходного языка. Формально L = {w R ½w Î L}.

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




©2015 studenchik.ru Все права принадлежат авторам размещенных материалов.

Президентские телки VIP эскорт