Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 27 стр.

   Также предполагается, что правые части правил, для которых совпадают левые части,
можно записать в одну строку с использованием разделителя. Так, правила вывода из
приведенного примера можно записать следующим образом: S → aSb | ab.

      4.3. Классификация грамматик

    Правила порождающих грамматик позволяют осуществлять преобразования строк.
Ограничения же на виды правил позволяют выделить классы грамматик. Рассмотрим
классификацию, которую предложил Н. Хомский.
    Грамматики типа 0 - это грамматики, на правила вывода которых нет ограничений.
    Грамматики типа 1, или контекcтные грамматики -это грамматики, все правила которых
имеют следующий вид: хАу → хϕу, где A ∈ VN, x, y, ϕ ∈ (VN ∪ VT)+.
    Грамматики типа 2 - это бесконтекстные, или контекстно-свободные грамматики (КС-
грамматики). Правила вывода для этих грамматик имеют следующий вид: А → ϕ, где А ∈
VN, ϕ ∈ (VN ∪ VT)*.
    Грамматики типа 3 - это автоматные грамматики, которые делятся на два типа:
    а) леволинейные (леворекурсивные), правила вывода для которых имеют следующий
вид: А → Аа | a, где А ∈ VN;
    б) праволинейные (праворекурсивные), правила вывода для которых имеют следующий
вид: А → Aа | a.
    Язык L называется языком типа i, если существует грамматика типа i, порождающая
язык L.

      4.3.1. Методика решения задач
     Пример 1. Дана порождающая грамматика G = (VT, VN, Р, S), в которой VT = {a, d, е}, VN
= {В, С, S}, Р = {S → аВ, В → Cd | dC, С → е}. Выписать терминальные цепочки,
порожденные данной грамматикой, и определить длину их вывода.
     Решение. Получим следующие терминальные цепочки:
     S → аВ → aCd → aed,
     S → аВ → adC → ade,
     длина вывода которых равна 3.
     Пример 2. Дана грамматика G = (VT, VN, Р, C), в которой VT = {a, b, c, d, е}, VN = {A, В,
С, D, E}, Р = {A → ed, В → Ab, С → Bc, С → dD, D → Ae, E → bc}. Определить,
принадлежит ли языку L(G) цепочка eadabcb.
     Решение. Выведем возможные терминальные цепочки из аксиомы с помощью заданных
правил вывода:
     С → Bc → Abc → edbc,
     С → dD → dAe → dede.
     Так как первые же терминальные символы полученных цепочек не совпадают с
заданной, можно сделать вывод о том, что цепочка eadabcb не принадлежит языку L(G).
     Пример 3. Построить КС-грамматику (грамматику типа 2), порождающую цепочки из 0
и 1 с одинаковым числом тех и других символов.
     Решение. Определим множества, задающие грамматику: VT = {0, 1}; VN = {S}; Р =
{S → 0S1, S → 1S0, S → ε, S → S01, S → S10}.
     Пример 4. Описать язык, порождаемый следующими правилами: S → bSS | а.
   Решение. Построим несколько терминальных цепочек, применяя заданные правила
вывода:
   S → a;
   S → bSS → baa;
   S → bSS → bbSSS → bbaaa;