Математическая логика и теория алгоритмов. Стенюшкина В.А. - 99 стр.

кая, что ωi+1 непосредственно выводима из ωI, i=0,1,…,n-1, ωi∈(N∪T)*. Запись
α⇒β.
       Определение Множество всех цепочек терминальных символов, выво-
димых из главного нетерминала, называется языком, порождённым этой грам-
матикой. Обозначение: L(G)={α| S⇒ α, α∈T*}.
       Пример - Грамматики G=: N={I}, T={a, b, c, ∨ , ∧ , ¬ , (,)},
S={I}, P={I→(I ∨ I), (I ∧ I), I→ ¬ I, I→a, I→b, I→c} описывает язык булевых фор-
мул с переменными a, b, c и логическими операциями ∨ , ∧ , ¬ . В частности,
имеет место вывод: I⇒(I ∨ I) ⇒((I ∧ I) ∨ I) ⇒((a ∧ b) ∨ c).
       Язык называется распознаваемым, если существует алгоритм, который
для произвольной цепочки за конечное число шагов даёт ответ на вопрос, при-
надлежит ли цепочка языку.

       6.4 Классификация языков по Хомскому

        Н. Хомский (американский лингвист) предложил классифицировать фо-
рмальные языки по типу правил порождающих их грамматик.
        Класс 0. Правила вывода имеют вид ϕ→ψ. Ограничений на строки ϕ, ψ
не вводится. Языки этого класса близки моделям естественных языков.
        Класс 1 Правила вывода имеют вид ϕ→ψ, где ϕ=ξ1αξ2, ψ=ξ1βξ2, α∈Ν,
β∈V , ξ1, ξ2 ∈V*.
     +

        Грамматика называется контекстной грамматикой. Языки, порождённые
грамматиками этого типа называются контекстно зависимыми. Относятся к чи-
слу легко распознаваемых.
        Пример – Грамматика G= : N={I, A, B, C, D}, T={a, b, c},
S={I}, P={I→ABA, B→ABCA, B→b, bC→bb, AC→DC, DC→DA, DA→CA,
A→a} имеет класс 1. Она порождает язык anbnan.
        Класс 2 Все порождающие правила имеют вид: A→β, где A –
нетерминальный символ, β∈V+. Грамматики этого класса называются контекс-
тно-свободными. Они играют главную роль при формальном изучении синтак-
тики языков программирования.
        Класс 3 Порождающее правила имеют вид: A→bB или A→b, где A,
B∈Ν, b∈T. Языки этого класса называются регулярными или автоматными, а
порождающие их грамматики – автоматными грамматиками. Используются на
этапе лексического анализа.
        Иерархия языков задаётся включением L0⊃L1⊃L2⊃L3.
        Из четырёх классов грамматик контекстно-свободные грамматики наи-
более приложимы к языкам программирования. С их помощью можно опреде-
лить значительную часть синтаксической структуры языка программирования.
Интересно отметить, что между НФБ и КС –грамматиками имеется тесная
связь; различия касаются лишь обозначений. В частности связке «: : =» из НФБ
соответствует отношение «→» в КС – грамматике, металингвистическим пере-
менным из НФБ соответствуют нетерминалы в КС – грамматике и т.д.