Теория формальных языков, грамматик и автоматов. Ишакова Е.Н. - 5 стр.

                   ся в виде α→β (читается: «из цепочки α выводится цепочка
                   β»);
           S - начальный символ грамматики, S ∈VN.
      Для записи правил вывода с одинаковыми левыми частями вида
α → β1, α → β 2 ,K,α → β n используется сокращенная форма записи
α → β1 | β 2 | K | β n .
      Пример 1.2. Грамматика G1=({0, 1}, {A, S}, P1, S), где множество Р1 со-
стоит из правил вида: 1) S→ 0A1; 2) 0A→ 00A1;      3) A→ε.
      Определение 1.7. Цепочка β ∈ (VT ∪ VN) непосредственно выводима из
                                               *


цепочки α ∈ (VT ∪ V N ) + в грамматике G = (VT , V N , P, S ) (обозначается: α⇒β),
если α = ξ1γξ 2 и β = ξ1δξ 2 , где ξ1, ξ 2 , δ ∈ (VT ∪ VN )* , γ ∈ (VT ∪ V N ) + и правило
вывода γ → δ содержится во множестве Р.
Определение 1.8. Цепочка β ∈ (VT ∪ VN)* выводима из цепочки α ∈ (VT ∪ V N ) + в
грамматике G = (VT , VN , P, S ) (обозначается α⇒*β), если существует последо-
 вательность цепочек γ 0 , γ 1 , K , γ n (n≥0) такая, что α = γ 0 ⇒ γ 1 ⇒ K ⇒ γ n = β .
      Пример 1.3. В грамматике G1 S⇒*000111, т.к. существует вывод
S ⇒ 0 A1 ⇒ 00 A11 ⇒ 000 A111 ⇒ 000111.
      Определение 1.9. Языком, порожденным грамматикой G = (VT , V N , P, S ) ,
называется множество всех цепочек в алфавите VT, которые выводимы из на-
чального символа грамматики S c помощью правил множества Р, т.е. множест-
во L(G ) = {α ∈ VT* | S ⇒ *α } .
     Пример 1.4. Для грамматики G1 L(G1)={0n1n | n>0}.
  Определение 1.10. Цепочка α ∈ (VT ∪ VN )* , для которой существует вывод
  S⇒*α, называется сентенциальной формой в грамматике G = (VT , V N , P, S ) .
      Определение 1.11. Грамматики G1 и G2 называются эквивалентными, ес-
ли L(G1 ) = L(G2 ) .
      Пример 1.5. Для грамматики G1 эквивалентной будет грамматика
G2 = ({0, 1}, {S}, P2, S), где множество правил вывода P2 содержит правила вида
S → 0S1 | 01.
                      Классификация грамматик по Хомскому
 Тип 0. Грамматика G = (VT , VN , P, S ) называется грамматикой типа 0, если на
 ее правила вывода не наложено никаких ограничений, кроме тех, которые ука-
                       заны в определении грамматики.
      Тип 1. Грамматика G = (VT , VN , P, S ) называется контекстно-зависимой
грамматикой (КЗ-грамматикой), если каждое правило вывода из множества Р
имеет вид α→β, где α ∈ (VT ∪ VN)+, β ∈ (VT ∪ VN)* и |α| ≤ |β|.



                                                                                        5