formal_languages_translation_theory (Формальные грамматики), страница 3

Справедливы следующие соотношения: любая регулярная грамматика является КС-грамматикой; любая неукорачивающая КС-грамматика является КЗ-грамматикой; любая неукорачивающая грамматика является грамматикой типа 0.Утверждение 5 следует непосредственно из определений.Рассматривая только неукорачивающие регулярные и неукорачивающие КСграмматики, что согласно утверждениям 2 и 4 не ограничивает классы соответствующихязыков, получаем следующую иерархию классов грамматик:неукорачивающие Регулярные  неукорачивающие КС  КЗ  Тип 0(Запись A  B означает, что A является собственным подклассом класса B.)Вместо класса КЗ-грамматик в данной иерархии можно указать более широкий класснеукорачивающих грамматик, которые, как известно, порождают те же языки, что и КЗграмматики.4)5)В разделе «Разбор по регулярным грамматикам» будет рассмотрен алгоритм построения по конечному автомату эквивалентной грамматики.

Построенная алгоритмом грамматика будет автоматной.Алгоритм устранения правил с пустой правой частью для КС-грамматик, приведенный в разделе «Преобразования грамматик», пригоден также и для устранения -правил из регулярных и автоматных грамматик.9Элементы теории формальных языков и грамматик / Классификация грамматик и языков по ХомскомуУтверждение 6.

Справедливы следующие соотношения: каждый регулярный язык является КС-языком, но существуют КС-языки, которыене являются регулярными, например:n nL  {a b | n  0}; каждыйКС-язык является КЗ-языком, но существуют КЗ-языки, которыене являются КС-языками, например:n n nL  {a b c | n  0}; каждый КЗ-язык является языком типа 0 (т. е. рекурсивно перечислимым языком),но существуют языки типа 0, которые не являются КЗ-языками, например: язык,состоящий из записей самоприменимых алгоритмов Маркова в некотором алфавите.

6)Из утверждения 6 следует иерархия классов языков:Тип 3 (Регулярные)  Тип 2 (КС)  Тип 1 (КЗ)  Тип 0Рис. 1. Иерархия классов языков.На рис. 1 иерархия Хомского для классов языков изображена в виде диаграммы Венна. Классы вкладываются друг в друга. Самый широкий класс языков (типа 0) содержит всебе все остальные классы.Утверждение 7. Проблема «Можно ли язык, описанный грамматикой типа k(k  0, 1, 2), описать грамматикой типа k  1?» является алгоритмически неразрешимой.Заметим, что для k  1, 2, 3 язык типа k является также и языком типа k  1 (согласноиерархии на рис.1, класс языков типа k является подклассом класса языков типа k  1).

Несмотря на то, что нет алгоритма, позволяющего по заданному описанию языка L (например,по грамматике), определить максимальное k, такое что L является языком типа k, при ответена вопрос «Какого типа заданный язык L?» в примерах и задачах будем указывать, если неоговорено иное, максимально возможное k (0, 1, 2, или 3) для заданного языка L.Рассмотрим, например, язык La,b  {a, b}, состоящий из двух однобуквенных цепочек.Какого типа язык La,b? Ответ: типа 3, так как, во-первых, он порождается грамматикой6)10Понятие записи нормального алгоритма Маркова определяется в [10].Элементы теории формальных языков и грамматик / Примеры грамматик и языковS → a | b типа 3; во-вторых, не существует грамматики типа k  3, которая бы порождала La,b(т.

е. 3 — это максимально возможное k, такое, что La,b является языком типа k).Отметим, что согласно иерархии языков, следующие утверждения также справедливы: «La,b является языком типа 2», «La,b является языком типа 1», «La,b является языком типа0». Но, с учетом вышесказанного, эти утверждения не считаются исчерпывающими ответамина вопрос «Какого типа язык La,b?».Соглашение: в примерах и задачах для краткости вместо полной четверки G   T, N,P, S  будем иногда выписывать только так называемую «схему» грамматики — правила вывода Р, считая, что большие латинские буквы обозначают нетерминальные символы, начальный символ (цель) грамматики обязательно стоит в левой части первого правила,  — пустаяцепочка, все остальные символы — терминальные.Задача.Даны грамматики G1 и G2:G1:S → 0A1A → 0A0A → (1) Какого типа язык L(G1)?G2:S→ aSb | (2) Какого типа язык L(G2)?Решение1) Правила грамматики G1 удовлетворяют ограничениям на правила КС-грамматик, ноне удовлетворяют ограничениям регулярных грамматик, т.

е. это грамматика типа 2, и поэтому L(G1) является языком типа 2 (следовательно, это язык и типа 1, и типа 0). Заметим,n n(2n  1)что L(G1)  {00 0 1 | n  0}  {01 | n  0} и этот язык является также языком типа 3, поскольку описывается следующей регулярной грамматикой:S → 0AA → 0B | 1B →0AИтак, максимальное k, для которого L(G1) является языком типа k, равно 3.2) По виду правил G2 является грамматикой типа 2 и не является грамматикой типа 3.Следовательно, L(G2) является языком типа 2. Является ли L(G2) языком типа 3? Ответ наэтот вопрос отрицательный, так как не существует регулярной грамматики (т.

е. грамматикиn nтипа 3), порождающей язык L(G2)  {a b | n  0}7).Итак, максимальное k, для которого L(G2) является языком типа k, равно 2.Примеры грамматик и языковПримеры грамматик и языков, иллюстрирующие классы иерархии Хомского, приведем в порядке, обратном классификации, т. е. будем идти от простого к сложному.7)Нерегулярность языка {anbn | n  0} будет доказана в разделе «Разбор по регулярным грамматикам».11Элементы теории формальных языков и грамматик / Примеры грамматик и языковРегулярные1) Грамматика S → aS | a является праволинейной (неукорачивающей) грамматикой.nОна порождает регулярный язык {a | n  0}. Этот язык может быть порожден и леволинейной грамматикой: S → Sa | a.

Заметим, что обе эти грамматики являются автоматными.2) Грамматика S → aS |  является праволинейной и порождает регулярный язык{a | n  0}. Для любого регулярного языка существует неукорачивающая регулярная грамматика (см. утверждение 4). Построим неукорачивающую регулярную грамматику для данного языка:nSА→ aA | a | → a | aAВ самом деле, правило с пустой правой частью может применяться только один раз итолько на первом шаге вывода; остальные правила таковы, что их правая часть не короче левой, т. е.

грамматика неукорачивающая.3) ГрамматикаS → A | BA → a | BaB →b | Bb | Abлеволинейная; она порождает регулярный язык, состоящий из всех непустых цепочекв алфавите {a, b}, заканчивающихся символом  (маркер конца) и не содержащих подцепочку aa. То есть в цепочках этого языка символ a не может встречаться два раза подряд, хотябы один символ b обязательно присутствует между любыми двумя a. С помощью теоретикомножественной формулы данный язык описывается так: { |   {a, b}, aa   }.Контекстно-свободные4) ГрамматикаS → aQb | accbQ → cScnnявляется контекстно-свободной (неукорачивающей) и порождает КС-язык {(ac) (cb) | n n n0}, который, как и встречавшийся нам ранее язык {a b | n  0}, не является регулярным, т. е.не может быть порожден ни одной регулярной грамматикой.5) ГрамматикаS → aSa | bSb | *порождает КС-язык {xx R, x{a, b} }.

Данный язык не является регулярным. Грамматика неудовлетворяет определению неукорачивающей, но для нее существует эквивалентная неукорачивающая грамматика (см. утверждение 2). Приведем такую грамматику:SA12→ A|→ aAa | bAb | aa | bbЭлементы теории формальных языков и грамматик / Примеры грамматик и языковНеукорачивающие и контекстно-зависимые6) Грамматика:S → aSBC | abCCB → BCbB → bbbC → bccC → ccнеукорачивающая и порождает язык {a nbnc n | n  0} , который является языком типа 1, но неявляется языком типа 2 (этот факт доказывается с помощью «леммы о разрастании цепочекКС-языка» [3, т.1]).Правило CB → BC не удовлетворяет определению КЗ-грамматики.

Однако, заменивэто правило тремя новыми CB→ СD, CD → BD, BD → BC (добавляем новый символ D вмножество нетерминалов N ), мы получим эквивалентную серию контекстно-зависимых правил, которые меняют местами символы C и B. Таким образом, получаем эквивалентную КЗграмматику:S → aSBC | abCCB → CDCD → BDBD → BCbB → bbbC → bccC → ccБез ограничений на вид правил (тип 0)7) В грамматике типа 0S → SSSS → второе правило не удовлетворяет ограничениям неукорачивающей грамматики. Существуетбесконечно много выводов в данной грамматике, однако порождаемый язык конечен и состоит из единственной цепочки: {}.Следующая грамматика также не является неукорачивающей и порождает пустойязык, так как ни одна терминальная цепочка не выводится из S (для обозначения пустогоязыка используется  — знак пустого множества):S → SSSS → Sa | SЗаметим, что языки L  {} и L   (пустой язык) могут быть описаны грамматиками типа 3.

Кроме того, отметим, что L  L, так как L не содержит цепочек вообще, а L— язык, состоящий из одной цепочки (пустая цепочка  по определению равноправна состальными цепочками в алфавите).8) Содержательные примеры грамматик, порождающих языки, не принадлежащиеклассу контекстно-зависимых (тип 1), не приводятся из-за их громоздкости. Ниже обсуждается лишь возможность построения такой грамматики для одного языка типа 0.Как известно, языки типа 0 (рекурсивно перечислимые множества) можно задавать спомощью распознавателей: НАМ или МТ. Существуют алгоритмы, позволяющие по НАМ13Элементы теории формальных языков и грамматик / Примеры грамматик и языковили МТ построить эквивалентную грамматику типа 0, задающую тот же язык, что и исходный распознаватель.Пусть задан некоторый алфавит.

Из теории алгоритмов известно, что можно построить НАМ A, на вход которому подается запись любого алгоритма (НАМ) X в заданном алфавите, и алгоритм A эмулирует работу алгоритма X в применении к записи X. Можно такжедобиться, чтобы A зацикливался, если ему подали на вход цепочку, не являющуюся правильной записью какого-либо алгоритма. Таким образом, алгоритм A останавливается только назаписях самоприменимых алгоритмов, а на всех других входах — зацикливается. Другимисловами, А задает язык записей самоприменимых алгоритмов, — обозначим этот язык Lself .Следовательно, Lself можно описать с помощью грамматики типа 0.Покажем, что не существует грамматики типа 1, которая порождает язык Lself . Известно, что проблема распознавания для грамматик типа 1 алгоритмически разрешима.

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