На головну

Критерії звичайно-автоматна мов

  1.  II. СЛОВО у мовній / МОВНОМУ МЕХАНІЗМ ЛЮДИНИ
  2.  IV. Мовний знак як лінгвістична категорія.
  3.  VIII. ТИПИ МОВНИХ ЗНАЧЕНЬ
  4.  А) Критерії
  5.  А. Критерії моногенного успадкування.
  6.  Антропогенез. Основні етапи процесу антропогенезу. Критерії людини.
  7.  Б12. 1. Види складів злочину і критерії їх класифікації.

Звичайно-автоматні мови можна охарактеризувати в термінах взаімозамещаемості слів. Введемо для цього необхідні поняття.

Нехай дано довільний мову A в алфавіті X, А також пара слів p, r в цьому ж алфавіті X (Допускаються і порожні слова).

слова p, r назвемо взаимозамещающие в мові A (позначення p » r (A)), якщо виконана умова: які б не були слова (можливо, порожні) x, y, слово xpy належить мові A тоді і тільки тоді, коли слово xry також належить мові A.

слова p, r назвемо левовзаімозамещаемимі (правовзаімозамещаемимі) В мові A (позначення відповідно p »л r (A)), p »п r (A)), якщо виконана умова: яке б не було слово x, слово px (відповідно xp) Належить мові A тоді і тільки тоді, коли слово rx (відповідно xr) Також належить мові A.

З цих визначень безпосередньо випливають наступні твердження:

  1. Ставлення взаімозамещаемості (правої, лівої) для слів є відношенням еквівалентності, І, отже, воно розбиває спільну мову в X (Т. Е. Безліч X * ^ = X * E {U} всіх, включаючи порожнє слово U, слів в X ) На класи взаімозамещаемості (відповідно правої, лівої взаімозамещаемості). його ранг (Т. Е. Потужність безлічі всіх класів еквівалентності) може виявитися нескінченним. Наприклад, нехай мова B складається з усіх слів, довжини яких є точними квадратами. Тоді, як неважко бачити [1], взаімозамещаеми лише такі слова, які мають однакову довжину. Оскільки взаімозамещаемость слів тягне за собою їх праву (ліву) взаімозамещаемость, то розбиття на класи взаімозамещаемості є більш дрібним, ніж розбиття на класи правої (лівої) взаімозамещаемості. Іншими словами, будь-який клас правої (лівої) взаімозамещаемості або є класом взаімозамещаемості, або розбивається на кілька таких класів.
  2. нехай p »л r; тоді для будь-яких x вернотакже px »л rx. Зокрема, додаток справа до левовзаімозамещаемим словами однієї і тієї ж букви перетворює їх знову-таки в левовзаімозамещаемие слова. Тому можна визначити операцію множення класу лівої взаімозамещаемості Ai на букву (будь-яку) a. Саме, твір Ai a - Це той клас лівої взаімозамещаемості, в який потрапляють всі слова виду pa, де pI Ai.
  3. Мова A являетсяоб'едіненіем деяких класів взаімозамещаемості (правою взаімозамещаемості, лівої взаімозамещаемості), породжених їм, або збігається з одним з цих класів.

Наступна теорема (наводимо її без доведення) розкриває зв'язок між рангом лівої взаімозамещаемості мови і числом станів представляє автомата.

ТЕОРЕМА 2. (I) якщо автомат M представляє мову A з лівої взаімозамещаемостью рангу m, то число станів в M не менше m. (II) Для будь-якого мови A з лівої взаімозамещаемостью рангу m існує представляє його автомат з m станами.

Один із критеріїв звичайно-автоматна мов задається цією теоремою як її

СЛІДСТВО. Для того, щоб мова A був кінцево-автоматних, необхідно і достатньо, щоб породжувана їм система класів лівої взаімозамещаемості була кінцевою.

Теорема 2 цієї статті не поширюється на правуювзаімозамещаемость. Однак потрібно мати на увазі наступне

ЗАУВАЖЕННЯ 2. відображенням A -1 мови A називається мова, що складається зі слів мови A, виписаних в зворотному порядку входжень букв. Наприклад, якщо a(1) a(2) ... a(N) I A, то a(N) ... a(2) a(1) I A-1.

Нехай ранг правойвзаімозамещаемості для мови A дорівнює m. Тоді таким же буде ранг лівої взаімозамещаемості відбитого мови A -1. Якщо при цьому m звичайно, то A -1 - Кінцево-автоматний мову. Можна показати, що при цьому також і A - звичайно-автоматний мову, проте число станів представляє автомата для A, взагалі кажучи, більше m.

КІНЕЦЬ

лекція 14

Теорема 2 і її наслідки дозволяють просто вказувати ефективні, але не звичайно-автоматні мови.

Розглянемо, наприклад, мова A, що складається з усіх слів виду 0n10n, Де 0n позначає слово їх n нулів (n = 1, 2, ...). Припустимо, що A - звичайно-автоматний мову; тоді серед слів 0, 00, 000, ... знайдеться пара левовзаімозамещаемих (адже згідно слідству з теореми 2 число класів лівої взаімозамещаемості має бути кінцевим). нехай 0k »л 0s (A). В такому випадку в A поряд зі словом 0k10k мало б міститися і слово 0s10k (0k =p, 0s = r, x = 10k, px = 0k10k,rx = 0 s10k), Яке, за умовою, не належить A. Протиріччя. Отже, мова A непредставім в кінцевому автоматі.

Це міркування насправді встановлює наступний загальний факт, який можна сформулювати в термінах отделимости мов.

Будемо говорити, що мова B відокремлює мова A1 від (непересічного з ним) мови A2, якщо B E A 1 і B C A 2 = ?.

Далі, мова A1 кінцево-автоматно відділимо від мови A2, якщо існує звичайно-автоматний мову B, що відокремлює A1 від A2 (В такому випадку, як легко бачити, і A2 звичайно відділимо від A1 мовою O B, а тому можна розглядати симетричне ставлення кінцево автоматної отделимости мов).

У нашому прикладі ми можемо тепер помітити, що мова {0n10n} Невіддільна звичайно-автоматно від мови {0k10 s} (K ? s).

Наведемо (без доказів) ще два результату, кожен з яких корисно розглядати як певний (умовний або безумовний) критерій звичайно-автоматна мов:

Перший результат.

Дотримуючись Ю. т. Медведєву, для фіксованого алфавіту X = {a1, a2, ..., am} назвемо елементарними наступні мови:

A1 - Мова, що складається з однобуквених слів, A 2 - Мова, що складається з двобуквений слів, B i - Мова, що складається з усіх слів, що закінчуються буквою ai (I ? m);

Ci - Мова, що складається з усіх слів довжини, неменшою ніж 2, в яких передостанній буквою є ai (I ? m).

Медведєв довів:

клас мов (в алфавіті X), які представлені в кінцевих автоматах, є найменший клас мов, що містить всі елементарні мови і замкнутий щодо об'єднання E, перетину C, доповнення O і двох наступних операцій, кожна з яких перетворює мову A в мову A ?:

1) A ? складається в точності з тих слів, які мають початковий шматок, що належить A.

2) нехай ai, aj - Деякі букви алфавіту X = {a1, a2, ..., Am}. A ? виходить з A, Якщо замінити в кожному слові з A всі входження букви ai входженнями літери aj.

Другий результат.

Для кожного n в алфавіті {0, 1} існує мова, можна подати у автоматі з n станами і такий, що відповідний відбитий язик не представимо ні в якому автоматі з числом станів, меншим ніж 2n. (Пор. З зауваженням 2.)

Третій.

нехай A - Кінцево-автоматний мову, який не має слів непарної довжини. Тоді ліві (праві) половини слів мови A утворюють звичайно-автоматний мову.

Четвертий.

нехай A - кінцево-автоматний мову, який містить тільки слова, довжини яких кратні трьом. Тоді мова, що складається з «середніх третин» слів мови A, є звичайно-автоматним. Однак мова, яка складається зі слів, отриманих в результаті видалення «середніх третин» зі слів мови A, Може не бути звичайно автоматним. (Переконатися в цьому можна на прикладі звичайно автоматного мови A, що складається з усіх довічних слів довжини, кратної трьом, які не містять поспіль двох одиниць.)

КІНЕЦЬ

лекція 15



© um.co.ua - учбові матеріали та реферати