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

Однако до сих пор открыт вопрос, существует ли для любого ЛОА эквивалентный ему детерминированный ЛОА.5Элементы теории формальных языков и грамматик / Основные понятия и определенияS→ 0A10A → 00A1A → *Определение: цепочка   ( T  N ) непосредственно выводима из цепочки  ( T  N ) в грамматике G   T, N, P, S  (обозначается  →G ), если   12,   12, где*1, 2,   (T  N ) ,   (T  N ) и правило вывода  →  содержится в P. Индекс G в обозначении →G обычно опускают, если понятно, о какой грамматике идет речь.Например, цепочка 00A11 непосредственно выводима из 0A1 в грамматике Gexample :0A1 → 00A11.

Здесь цепочка 0A, подчеркнутая двойной чертой, играет роль подцепочки  изопределения, цепочка 00A1 играет роль подцепочки , 1  , 2  1.*Определение:цепочка  (T  N )выводимаизцепочки  (T  N) в грамматике G  T, N, P, S  (обозначается  G ), если существуют цепочки 0, 1, ..., n (n  0), такие, что   0 → 1 → ... → n  . Последовательность0, 1, ..., n называется выводом длины n. Индекс G в обозначении G опускают, если понятно, какая грамматика подразумевается.Например, S  000A111 в грамматике Gexample (см. пример выше), т.к. существует вывод S → 0A1 → 00A11 → 000A111.

Длина вывода равна 3.Определение: языком, порождаемым грамматикой G   T, N, P, S , называетсямножество L(G)  {  T * | S  }.Другими словами, L(G) — это все цепочки в алфавите T, которые выводимы из S сn nпомощью правил P. Например, L(Gexample)  {0 1 | n  0}.Определение: цепочка   (T  N)*, для которой S  , называется сентенциальнойформой в грамматике G   T, N, P, S .Таким образом, язык, порождаемый грамматикой, можно определить как множествотерминальных сентенциальных форм.Определение: грамматики G1 и G2 называются эквивалентными, еслиL(G1)  L(G2).Пример. Грамматики G1  {0,1}, {A,S}, P1, S  и G2  {0,1}, {S}, P2, S  с правиламиP1:P2:S → 0A1S → 0S1 | 010A → 00A1A → n nэквивалентны, т.

к. обе порождают язык L(G1)  L(G2)  {0 1 | n  0}.Определение:грамматикиG1иG2почтиэквивалентны,еслиL(G1)  {}  L(G2)  {}.Другими словами, грамматики почти эквивалентны, если языки, ими порождаемые,отличаются не более, чем на .Например, почти эквивалентны грамматикиG1  {0,1}, {A, S}, P1, S 6иG2  {0, 1}, {S}, P2, S  с правиламиЭлементы теории формальных языков и грамматик / Классификация грамматик и языков по ХомскомуP1:P2:S → 0A10A → 00A1A →n nS → 0S1 | ,n nтак как L(G1)  {0 1 | n  0}, а L(G2)  {0 1 | n  0}, т.

е. L(G2) состоит из всех цепочек языка L(G1) и пустой цепочки, которая в L(G1) не входит.Классификация грамматик и языков по ХомскомуОпределим с помощью ограничений на вид правил вывода четыре типа грамматик:тип 0, тип 1, тип 2, тип 3. Каждому типу грамматик соответствует свой класс 3) языков. Еслиязык порождается грамматикой типа i (для i  0, 1, 2, 3), то он является языком типа i.Тип 0Любая порождающая грамматика является грамматикой типа 0. На вид правил грамматик этого типа не накладывается никаких дополнительных ограничений. Класс языков типа 0 совпадает с классом рекурсивно перечислимых языков.Грамматики с ограничениями на вид правил выводаТип 1Грамматика G   T, N, P, S  называется неукорачивающей, если правая часть каждогоправила из P не короче левой части (т.

е. для любого правила  →   P выполняется неравенство |  |  |  | ). В виде исключения в неукорачивающей грамматике допускается наличие правила S → , при условии, что S (начальный символ) не встречается в правых частяхправил.Грамматикой типа 1 будем называть неукорачивающую грамматику.Тип 1 в некоторых источниках определяют с помощью так называемых контекстнозависимых грамматик.Грамматика G   T, N, P, S  называется контекстно-зависимой (КЗ), если каждое*правило из P имеет вид  → , где   1A2,   12, A  N,   (T  N ), 1, 2  (T  N) .В виде исключения в КЗ-грамматике допускается наличие правила с пустой правой частьюS → , при условии, что S (начальный символ) не встречается в правых частях правил.Цепочку 1 называют левым контекстом, цепочку 2 называют правым контекстом.

Язык, порождаемый контекстно-зависимой грамматикой, называется контекстнозависимым языком.ЗамечаниеИз определений следует, что если язык, порождаемый контекстно-зависимой или неукорачивающей грамматикой G   T, N, P, S , содержит пустую цепочку, то эта цепочка выводится в G заодин шаг с помощью правила S → . Других выводов для  не существует. Если среди правил Pнет правила S → , то порождаемый контекстно-зависимой или неукорачивающей грамматикойG язык не содержит пустую цепочку .3)Классом обычно называют множество, элементы которого сами являются множествами.7Элементы теории формальных языков и грамматик / Классификация грамматик и языков по ХомскомуУтверждение 1.

Пусть L — формальный язык. Следующие утверждения эквивалентны:1) существует контекстно-зависимая грамматика G1, такая что L  L(G1);2) существует неукорачивающая грамматика G2, такая что L  L(G2).Очевидно, что из (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 — формальный язык. Следующие два утверждения эквивалентны: существует праволинейная грамматика G1, такая что L  L(G1); существует леволинейная грамматика G2, такая что L  L(G2).8Элементы теории формальных языков и грамматик / Классификация грамматик и языков по ХомскомуИз утверждения 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.