Визначення 4.20

• Граматиками типу 0 називають довільні породжуючі граматики загального виду, що не мають жодних обмежень на правила виводу.

Цілком очевидно, що так введенне відношення ≈ є відношенням еквівалентності (рефлексивним, симетричним та транзитивним відношенням). Це дозволяє нам говорити про те, що різні варіанти визначень граматик (породжуючі та конктекстні) є еквівалентними, і що ієрархія Хомского досить стабільна відносно варіантів граматик.

23. Еквівалентність машин Тьюрінга та породжуючих граматик

Машиною Тюрінга M називається послідовність

параметрів (Q, A, #, δ, q 0, F), де

• Q – скінченна множина станів,

• A – скінченний алфавіт (Q ∩ A =∅),

• # – символ з A (≪ порожній≫ символ),

• q 0 – початковий стан із Q,

• F – підмножина фінальних станів із Q.

Зауважимо, що є багато варіантів визначення машин Тьюрінга, наприклад, може бути декілька стрічок, порожній символ можна явно не вводити в алфавіт і вважати його однаковим для класу машин Тьюрінга, не вводити заключних станів і таке інше. Всі такі визначення, як правило, є еквівалентними з точки зору сприйняття мов.

Наведений у попередньому прикладі протокол машини Тьюрінга підказує ідею побудови породжуючої граматики за програмою машини. Таку побудову зробимо в два етапи: спочатку за програмою побудуємо продукції переходу (перетворення) конфігурацій машини Тьюрінга, потім зробимо обернення побудованих продукцій та добавимо правило для аксіоми та правила породження і видалення порожніх символів. Отримана породжуюча граматика буде еквівалентна вибраній машині Тьюрінга.

Кожна команда машини Тьюрінга породжує наступні правила перетворення конфігурацій:

• Команда виду qa → pbR породжує правило qa → bp.

• Команда виду qa → pbL породжує множину правил перетворення { cqa → pcb | с∈ A }.

• Команда виду qa → pb породжує правило qa → pb.

На другому етапі побудови обернемо отримані правила (перетворення виду α → β замінимо на правило породжуючоїграматики β → α), добавимо правило для аксіоми S → # qF #. Враховуючи, що при таких побудованих простих правилах можуть бути зайві #, переведемо їх в пустий ланцюжок ε правилом #→ ε, або створимо у разі необхідності додаткові порожні символи # правилом #→ ##. Нарешті, потрібно буде видалити початковий стан, щоб отримати

(породити) початковий ланцюжок правилом q0 → ε.

Таким чином, буде створена граматика GM =(N, T, P, S), яка має наступні параметри:

• N ={ S }∪ Q ∪ {#} (S ∉ Q ∪ {#}).

• T = A \{#}.

• S ∈ N.

• P будується за вказаним вище алгоритмом.__

24. Лінійно-обмежені автомати. Магазинні автомати

Лінійно-обмежені автомати можуть розглядатися як обмежені машини Тьюрінга, коли довжина ланцюжка на стрічні завжди лінійно обмежена довжиною вхідного ланцюжка. Визначення 4.28 Машина Тьюрінга M =(Q, A, #, δ, q0, F) називається лінійно-обмеженим автоматом, якщо існує число k, що

для будь якого ланцюжка v ∈ A * довжини n, з умови # q0v # |–*# w1q w2 # (q ∈ Q, w1, w2 ∈ A *) випливає, що | w1 w2 | ≤ k ⋅ n.

Наведену умову важко перевірити, маючи машину Тьюрінга, тому наведене визначення часто спрощують, вимагаючи, щоб k = 1, тобто, щоб голівка машини Тьюрінга не могла записувати нові символи за межами вхідного ланцюжка. Є і інші варіанти визначення лінійно- обмежених автоматів.

Використовуючи методи, наведені в попередньому підрозділі, можемо за лінійно-обмеженим автоматом побудувати еквівалентну породжуючу граматику типу 1, і навпаки, за граматикою типу 1 побудувати лінійно-обмежений автомат. Таким чином, справедливе наступне твердження.

Теорема 4.5 За кожним лінійно-обмеженим автоматом можна побудувати еквівалентну йому породжуючу граматику типу 1, і навпаки, за кожною породжуючою граматикою типу 1 можна побудувати еквівалентний їй лінійно-обмежений автомат. Говорячи більш просто, теорема стверджує, що клас лінійно- обмежених автоматів еквівалентний класу породжуючих граматик

типу 1.