Студопедия

КАТЕГОРИИ:

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



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

Читайте также:
  1. IV.4.3) Общий ход формулярного процесса.
  2. Вопрос 12. Общий порядок назначения и исчисления пенсий
  3. Вопрос 4.5.4. Общий порядок действий при оказании первой помощи пострадавшему на месте происшествия
  4. Вопрос 61. Общий надзор прокуратуры.
  5. Вопрос. Материалистическая диалектика как всеобщий метод познания и преобразования мира
  6. Всеобщий метод криминалистической науки
  7. Глава 1. ОБЩИЙ УХОД ЗА БОЛЬНЫМИ. ЛЕЧЕБНО-ДИАГНОСТИЧЕСКИЕ ПРОЦЕДУРЫ
  8. Защита с помощью R-C цепочек.
  9. Методы анализа КС-языков. Грамматики предшествования
  10. Название таблицы (общий заголовок)

 

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

Теорема 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}.

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

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

 


Дата добавления: 2014-11-13; просмотров: 22; Нарушение авторских прав


<== предыдущая лекция | следующая лекция ==>
Обобщенные КС-грамматики и приведение их к удлиняющей | Операции над языками
lektsii.com - Лекции.Ком - 2014-2018 год. (0.01 сек.) Главная страница Случайная страница Контакты