Визначення 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 породжує множину правил перетворення с∈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.


0444108050474980.html
0444165458509220.html
    PR.RU™