Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Визначення 4.20






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

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


 

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

 

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

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

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

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

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

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

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

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

 

 

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

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

• Команда виду qapbR породжує правило qabp.

• Команда виду qapbL породжує множину правил перетворення { cqapcb | с∈A}.

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

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

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

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

N={S}∪Q∪{#} (SQ∪{#}).



T=A\{#}.

SN.

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


 

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

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

для будь якого ланцюжка vA* довжини n, з умови #q0v# |–*#w1q w2# (qQ, w1, w2A*) випливає, що |w1 w2| ≤ kn.

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

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

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

типу 1.


mylektsii.ru - Мои Лекции - 2015-2020 год. (0.023 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал