Учебное пособие для студентов II курса (издание третье, переработанное и дополненное) Москва 2009 удк 519. 682. 1
 Скачать 2.2 Mb.
|
|
Замечание Из определений следует, что если язык, порождаемый контекстно-зависимой или неукорачива- ющей грамматикой G T, N, P, S , содержит пустую цепочку, то эта цепочка выводится в G за один шаг с помощью правила S → . Других выводов для не существует. Если среди правил P нет правила S → , то порождаемый контекстно-зависимой или неукорачивающей грамматикой G язык не содержит пустую цепочку 3) Классом обычно называют множество, элементы которого сами являются множествами. Элементы теории формальных языков и грамматик / Классификация грамматик и языков по Хомскому 8 Утверждение 1. Пусть L—формальный язык. Следующие утверждения эквивалент- ны: 1) существует контекстно-зависимая грамматика G 1 , такая что L L(G 1 ); 2) существует неукорачивающая грамматика G 2 , такая что L L(G 2 ). Очевидно, что из (1) следует (2): любая контекстно-зависимая грамматика удовлетво- ряет ограничениям неукорачивающей грамматики (см. определения). Доказательство в об- ратную сторону основывается на том, что можно каждое неукорачивающее правило заме- нить эквивалентной серией контекстно-зависимых правил. Из утверждения 1 следует, что язык, порождаемый неукорачивающей грамматикой, контекстно-зависим. Таким образом, неукорачивающие и КЗ-грамматики определяют один и тот же класс языков. Тип 2 Грамматика G T, N, P, S называется контекстно-свободной (КС), если каждое правило из Р имеет вид A → , где A N, ( T N ) * Заметим, что в КС-грамматиках допускаются правила с пустыми правыми частями. Язык, порождаемый контекстно-свободной грамматикой, называется контекстно- свободным языком. Грамматикой типа 2 будем называть контекстно-свободную грамматику. КС-грамматика может являться неукорачивающей, т.е. удовлетворять ограничениям неукорачивающей грамматики. Утверждение 2. Для любой КС-грамматики G существует неукорачивающая КС- грамматика G', такая что L(G) L(G'). Согласно утверждению 2, любой контекстно-свободный язык порождается неукора- чивающей контекстно-свободной грамматикой. Как следует из определений, такая КС- грамматика может содержать не более одного правила с пустой правой частью, причем это правило имеет вид S → , где S — начальный символ, и при этом никакое правило из P не содержит S в своей правой части. В разделе «Преобразования грамматик» будет приведен алгоритм, позволяющий устранить из любой КС-грамматики все правила с пустыми правыми частями (в получив- шейся грамматике может быть правило S → в случае, если пустая цепочка принадлежит языку, при этом начальный символ S не будет входить в правые части правил). Тип 3 Грамматика G T, N, P, S называется праволинейной, если каждое правило из Р имеет вид A → wB либо A → w, где A, B N, w T * Грамматика G T, N, P, S называется леволинейной, если каждое правило из Р име- ет вид A → Bw либо A → w, где A, B N, w T * Утверждение 3. Пусть L—формальный язык. Следующие два утверждения эквива- лентны: существует праволинейная грамматика G 1 , такая что L L(G 1 ); существует леволинейная грамматика G 2 , такая что L L(G 2 ). Элементы теории формальных языков и грамматик / Классификация грамматик и языков по Хомскому 9 Из утверждения 3 следует, что праволинейные и леволинейные грамматики опреде- ляют один и тот же класс языков. Такие языки называются регулярными. Право- и леволи- нейные грамматики также будем называть регулярными. Регулярная грамматика является грамматикой типа 3. Автоматной грамматикой называется праволинейная (леволинейная) грамматика, такая, что каждое правило с непустой правой частью имеет вид: A → a либо A → aB (для леволинейной, соответственно, A → a либо A → Ba), где A, B N, a T. 4) Автоматная грамматика является более простой формой регулярной грамматики. Су- ществует алгоритм, позволяющий по регулярной (право- или леволинейной) грамматике по- строить соответствующую автоматную грамматику. Таким образом, любой регулярный язык может быть порожден автоматной грамматикой. Кроме того, существует алгоритм, позволя- ющий устранить из регулярной (автоматной) грамматики все -правила (кроме S → в слу- чае, если пустая цепочка принадлежит языку; при этом S не будет встречаться в правых ча- стях правил) 5) . Поэтому справедливо: Утверждение 4. Для любой регулярной (автоматной) грамматики G существует не- укорачивающая регулярная (автоматная) грамматика G′, такая что L(G) L(G′). Иерархия Хомского Утверждение 5. Справедливы следующие соотношения: любая регулярная грамматика является КС-грамматикой; любая неукорачивающая КС-грамматика является КЗ-грамматикой; любая неукорачивающая грамматика является грамматикой типа 0. Утверждение 5 следует непосредственно из определений. Рассматривая только неукорачивающие регулярные и неукорачивающие КС- грамматики, что согласно утверждениям 2 и 4 не ограничивает классы соответствующих языков, получаем следующую иерархию классов грамматик: неукорачивающие Регулярные неукорачивающие КС КЗ Тип 0 (Запись A B означает, что A является собственным подклассом класса B.) Вместо класса КЗ-грамматик в данной иерархии можно указать более широкий класс неукорачивающих грамматик, которые, как известно, порождают те же языки, что и КЗ- грамматики. 4) В разделе «Разбор по регулярным грамматикам» будет рассмотрен алгоритм построения по конечному ав- томату эквивалентной грамматики. Построенная алгоритмом грамматика будет автоматной. 5) Алгоритм устранения правил с пустой правой частью для КС-грамматик, приведенный в разделе «Преобра- зования грамматик», пригоден также и для устранения -правил из регулярных и автоматных грамматик. Элементы теории формальных языков и грамматик / Классификация грамматик и языков по Хомскому 10 Утверждение 6. Справедливы следующие соотношения: каждый регулярный язык является КС-языком, но существуют КС-языки, которые не являются регулярными, например: L {a n b n | n 0}; каждый КС-язык является КЗ-языком, но существуют КЗ-языки, которые не являются КС-языками, например: L {a n b n c n | 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. Рассмотрим, например, язык L a,b {a, b}, состоящий из двух однобуквенных цепочек. Какого типа язык L a,b ? Ответ: типа 3, так как, во-первых, он порождается грамматикой 6) Понятие записи нормального алгоритма Маркова определяется в [10]. Элементы теории формальных языков и грамматик / Примеры грамматик и языков 11 S → a | b типа 3; во-вторых, не существует грамматики типа k 3, которая бы порождала L a,b (т. е. 3 — это максимально возможное k, такое, что L a,b является языком типа k). Отметим, что согласно иерархии языков, следующие утверждения также справедли- вы: «L a,b является языком типа 2», «L a,b является языком типа 1», «L a,b является языком типа 0». Но, с учетом вышесказанного, эти утверждения не считаются исчерпывающими ответами на вопрос «Какого типа язык L a,b ?». Соглашение: в примерах и задачах для краткости вместо полной четверки G T, N, P, S будем иногда выписывать только так называемую «схему» грамматики — правила вы- вода Р, считая, что большие латинские буквы обозначают нетерминальные символы, началь- ный символ (цель) грамматики обязательно стоит в левой части первого правила, — пустая цепочка, все остальные символы — терминальные. Задача. Даны грамматики G 1 и G 2 : G 1 : S → 0A1 A → 0A0 A → G 2 : S → aSb | (1) Какого типа язык L(G 1 )? (2) Какого типа язык L(G 2 )? Решение 1) Правила грамматики G 1 удовлетворяют ограничениям на правила КС-грамматик, но не удовлетворяют ограничениям регулярных грамматик, т. е. это грамматика типа 2, и по- этому L(G 1 ) является языком типа 2 (следовательно, это язык и типа 1, и типа 0). Заметим, что L(G 1 ) {00 n 0 n 1 | n 0} {0 (2 n 1) 1 | n 0} и этот язык является также языком типа 3, по- скольку описывается следующей регулярной грамматикой: S → 0A A → 0B | 1 B → 0A Итак, максимальное k, для которого L(G 1 ) является языком типа k, равно 3. 2) По виду правил G 2 является грамматикой типа 2 и не является грамматикой типа 3. Следовательно, L(G 2 ) является языком типа 2. Является ли L(G 2 ) языком типа 3? Ответ на этот вопрос отрицательный, так как не существует регулярной грамматики (т. е. грамматики типа 3), порождающей язык L(G 2 ) {a n b n | n 0} 7) Итак, максимальное k, для которого L(G 2 ) является языком типа k, равно 2. Примеры грамматик и языков Примеры грамматик и языков, иллюстрирующие классы иерархии Хомского, приве- дем в порядке, обратном классификации, т. е. будем идти от простого к сложному. 7) Нерегулярность языка {a n b n | n 0} будет доказана в разделе «Разбор по регулярным грамматикам». Элементы теории формальных языков и грамматик / Примеры грамматик и языков 12 Регулярные 1) Грамматика S → aS | a является праволинейной (неукорачивающей) грамматикой. Она порождает регулярный язык {a n | n 0}.Этот язык может быть порожден и леволиней- ной грамматикой: S → Sa | a. Заметим, что обе эти грамматики являются автоматными. 2) Грамматика S → aS | является праволинейной и порождает регулярный язык {a n | n 0}.Для любого регулярного языка существует неукорачивающая регулярная грам- матика (см. утверждение 4). Построим неукорачивающую регулярную грамматику для дан- ного языка: S → aA | a | А → a | aA В самом деле, правило с пустой правой частью может применяться только один раз и только на первом шаге вывода; остальные правила таковы, что их правая часть не короче ле- вой, т. е. грамматика неукорачивающая. 3) Грамматика S → A | B A → a | Ba B → b | Bb | Ab леволинейная; она порождает регулярный язык, состоящий из всех непустых цепочек в алфавите {a, b}, заканчивающихся символом (маркер конца) и не содержащих подцепоч- ку aa. То есть в цепочках этого языка символ a не может встречаться два раза подряд, хотя бы один символ b обязательно присутствует между любыми двумя a. С помощью теоретико- множественной формулы данный язык описывается так: { | {a, b} , aa }. Контекстно - свободные 4) Грамматика S → aQb | accb Q → cSc является контекстно-свободной (неукорачивающей) и порождает КС-язык {(ac) n (cb) n | n 0}, который, как и встречавшийся нам ранее язык {a n b n | n 0}, не является регулярным, т. е. не может быть порожден ни одной регулярной грамматикой. 5) Грамматика S → aSa | bSb | порождает КС-язык {xx R , x {a, b} * }. Данный язык не является регулярным. Грамматика не удовлетворяет определению неукорачивающей, но для нее существует эквивалентная неуко- рачивающая грамматика (см. утверждение 2). Приведем такую грамматику: S → A | A → aAa | bAb | aa | bb Элементы теории формальных языков и грамматик / Примеры грамматик и языков 13 Неукорачивающие и контекстно - зависимые 6) Грамматика: S → aSBC | abC CB → BC bB → bb bC → bc cC → cc неукорачивающая и порождает язык } 0 | { n c b a n n n , который является языком типа 1, но не является языком типа 2(этот факт доказывается с помощью «леммы о разрастании цепочек КС-языка» [3, т.1]). Правило CB → BC не удовлетворяет определению КЗ-грамматики. Однако, заменив это правило тремя новыми CB→ СD, CD → BD, BD → BC (добавляем новый символ D в множество нетерминалов N ), мы получим эквивалентную серию контекстно-зависимых пра- вил, которые меняют местами символы C и B. Таким образом, получаем эквивалентную КЗ- грамматику: S → aSBC | abC CB → CD CD → BD BD → BC bB → bb bC → bc cC → cc Без ограничений на вид правил (тип 0) 7) В грамматике типа 0 S → SS SS → второе правило не удовлетворяет ограничениям неукорачивающей грамматики. Существует бесконечно много выводов в данной грамматике, однако порождаемый язык конечен и со- стоит из единственной цепочки: { }. Следующая грамматика также не является неукорачивающей и порождает пустой язык, так как ни одна терминальная цепочка не выводится из S (для обозначения пустого языка используется — знак пустого множества): S → SS SS → Sa | S Заметим, что языки L { } и L (пустой язык) могут быть описаны граммати- ками типа 3. Кроме того, отметим, что L L , так как L не содержит цепочек вообще, а L — язык, состоящий из одной цепочки (пустая цепочка по определению равноправна с остальными цепочками в алфавите). 8) Содержательные примеры грамматик, порождающих языки, не принадлежащие классу контекстно-зависимых (тип 1), не приводятся из-за их громоздкости. Ниже обсужда- ется лишь возможность построения такой грамматики для одного языка типа 0. Как известно, языки типа 0 (рекурсивно перечислимые множества) можно задавать с помощью распознавателей: НАМ или МТ. Существуют алгоритмы, позволяющие по НАМ Элементы теории формальных языков и грамматик / Примеры грамматик и языков 14 или МТ построить эквивалентную грамматику типа 0, задающую тот же язык, что и исход- ный распознаватель. Пусть задан некоторый алфавит. Из теории алгоритмов известно, что можно постро- ить НАМ A, на вход которому подается запись любого алгоритма (НАМ) X в заданном алфа- вите, и алгоритм A эмулирует работу алгоритма X в применении к записи X. Можно также добиться, чтобы A зацикливался, если ему подали на вход цепочку, не являющуюся правиль- ной записью какого-либо алгоритма. Таким образом, алгоритм A останавливается только на записях самоприменимых алгоритмов, а на всех других входах — зацикливается. Другими словами, А задает язык записей самоприменимых алгоритмов, — обозначим этот язык L self Следовательно, L self можно описать с помощью грамматики типа 0. Покажем, что не существует грамматики типа 1, которая порождает язык L self . Из- вестно, что проблема распознавания для грамматик типа 1 алгоритмически разрешима. То есть существует алгоритм, который определяет, принадлежит ли заданная цепочка языку, порождаемому грамматикой. Предположим, существует грамматика типа 1, порождающая язык L self . Тогда алгоритм распознавания дает ответ для любой цепочки, является ли она за- писью самоприменимого алгоритма или нет. Имеем противоречие с известным фактом об алгоритмической неразрешимости проблемы самоприменимости. Следовательно, граммати- ки типа 1, порождающей язык L self , не существует. Замечание о связи между языком и грамматикой В приведенных ранее примерах мы утверждали, что заданная грамматика порождает определенный язык исходя из нестрогих рассуждений, интуитивно, по совокупности правил вывода. Вообще говоря, следует доказывать, что заданная грамматика порождает нужный язык. Для этого требуется доказать, что в данной грамматике: I ) выводится любая цепочка, принадлежащая языку, II ) не выводятся никакие другие цепочки. |