Page 17 - 4761

- вмістом зовнішньої пам’яті.
Для розпізнавача завжди задається конфігурація, яка вважається початковою
конфігурацією. А початкова конфігурація зчитуючої головки бачить перший символ
вхідного ланцюга, пристрій керування знаходиться в заданому початковому стані, а
зовнішня пам'ять або пуста, або містить строго визначену конфігурацію.
Крім початкового стану для розпізнавача задається одна або декілька кінцевих
конфігурацій. В кінцевій конфігурації зчитуюча головка, як правило, знаходиться за
кінцем вихідного ланцюга (часто для розпізнавачів вводиться спеціальний символ, який
означає кінець ланцюга ).
Розпізнавач допускає вхідний ланцюг α, якщо, знаходячись в початковій
конфігурації і отримавши на вхід цей ланцюг, він може виконати послідовність кроків, які
закінчуються однією з його кінцевих конфігурацій. Мова, яка визначається
розпізнавачем– множина всіх ланцюгів, які допускає розпізнавач.
В и д и р о з п і з н а в а ч і в .
Розпізнавачі класифікують залежно від вигляду складових їхніх компонент:
зчитуючого пристрою, пристрою керування і зовнішньої памяті.
По вигляду зчитуючого пристрою: двосторонні та односторонні.
Односторонні допускають переміщення зчитуючої головки по стрічці вхідних
символів тільки в одному напрямі ( як правило лівосторонні).
По виду пристрою керування розпізнавачі бувають детерміновані і
недетерміновані. Розпізнавач називається детермінованим, якщо для кожної допустимої
конфігурації розпізнавача, яка виникла на деякому кроці його роботи, існує єдино
можлива конфігурація, в яку він перейде на наступному кроці роботи. Інакше він є
недетермінованим. Він може мати таку допустиму конфігурацію, для якої існує кінцева
множина конфігурацій, можливих на наступному кроці роботи.
По виду зовнішньої памяті:
1) розпізнавачі без зовнішньої памяті - зовнішня пам'ять повністю відсутня. В
процесі роботи використовується тільки кінцева пам'ять пристрою керування;
2) розпізнавачі з обмеженою зовнішньою пам’ятю – розмір зовнішньої пам’яті
обмежений залежно від довжини вхідного ланцюга символів;
3) hозпізнавачі з необмеженою зовнішньою пам’ятю - пам'ять з довільним
методом доступу.
Класифікація розпізнавачів за типом мови. Тип розпізнавача в класифікації
визначає складність його створення, а значить, складність розробки відповідного
програмного забезпечення для компілятора. Чим вище в класифікації стоїть розпізнавач,
тим складніше створити алгоритм, який забезпечує його роботу. Розробляти двосторонні
складніше, ніж односторонні. Недетерміновані складніше ніж детерміновані. Але
складність розпізнавача напряму зв’язана з типом мови.
Ми визначили 4 типи мови, отже для кожного з цих типів є свій вид розпізнавача з
визначеним набором компонент і відповідно, з заданою складністю алгоритма роботи.
Тип 0: необхідний розпізнавач, рівносильний машині Тьюрінга – недетермінований
двосторонній автомат, який має необмежену зовнішню пам'ять.
Тип 1: двосторонні недетерміновані автомати з обмеженою зовнішньою памятю.
Алгоритм роботи такого автомата має експоненціальну складність.
Тип 2: односторонні недетерміновані автомати з стековою зовнішньою памятю –
МП-автомати.
Тип 3: односторонні недетерміновані автомати без зовнішньої памяті – кінцеві
автомати. Простота і висока швидкість роботи розпізнавачів цього типу забезпечують
широку область застосування регулярних мов.

15