И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1114891), страница 2
Текст из файла (страница 2)
→ γ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:S → 0A10A → 00A1A →εn nP2:S → 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, которые не являются КЗ-языками, например: язык,состоящий из записей самоприменимых алгоритмов Маркова в некотором алфавите. 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(т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
