И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1119400), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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. Справедливы следующие соотношения: любая регулярная грамматика является КС-грамматикой; любая неукорачивающая КС-грамматика является КЗ-грамматикой; любая неукорачивающая грамматика является грамматикой типа 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, которые не являются КЗ-языками, например: язык,состоящий из записей самоприменимых алгоритмов Маркова в некотором алфавите.

Характеристики

Список файлов книги