ланцюжка символів визначити, чи належить вона заданому мови. Це один із способів завдання мови.
Розпізнавач входить до складу компілятора і є частиною програмного забезпечення комп'ютера. На малюнку 4.1 представлена ??умовна схема распознавателя.
Малюнок 4.31 - Умовна схема распознавателя
Основні компоненти распознавателя:
вхідна стрічка - лінійна послідовність клітин, або осередків, кожна з яких містить рівно один символ вхідного алфавіту;
вхідна (зчитує) головка оглядає одну вхідну осередок; на кожному кроці роботи може зрушуватися на одну клітинку вправо, вліво або залишатися на місці;
пристрій управління (УУ), яке координує роботу распознавателя, має деяке безліч станів і кінцеву пам'ять;
зовнішня (робоча) пам'ять може зберігати деяку інформацію в процесі роботи розпізнавача і може мати необмежений обсяг.
Алфавіт распознавателя конечен; він включає в себе всі допустимі символи вхідних ланцюжків, а також деякий додатковий алфавіт символів, які можуть оброблятися УУ і зберігатися в робочій пам'яті распознавателя.
В процесі своєї роботи распознаватель може виконувати деякі елементарні операції, такі як читання вхідного символу, зрушення головки, доступ до робочої пам'яті для читання або запису інформації, зміна стану УУ.
Робота распознавателя складається з послідовності кроків, або тактів. Те, яким повинен бути цей такт, визначається поточним вхідним символом, станом УУ і символом, витягнутим з пам'яті.
Такт складається з наступних моментів:
вхідна головка распознавателя зсувається на одну клітинку вправо, вліво або залишається на місці;
в пам'ять поміщається деяка інформація;
змінюється стан УУ.
У процесі роботи розпізнавача відбувається зміна конфігурацій. Конфігурація распознавателя (миттєве опис) визначається наступними параметрами:
стан УУ;
вміст вхідний стрічки і положення голівки, що зчитує в ній;
вміст зовнішньої пам'яті.
Конфігурація називається початковою, якщо УУ знаходиться в початковому стані, вхідна головка оглядає самий лівий символ на вхідних стрічці, а пам'ять має заздалегідь встановлений початкове вміст.
Конфігурація називається заключній, якщо УУ знаходиться в одному з безлічі заключних станів, а вхідні головка оглядає правий кінцевий маркер або зійшла з стрічки.
Розпізнавач допускає вхідну ланцюжок символів, якщо, перебуваючи в початковій конфігурації, в якій дана ланцюжок записана на вхідних стрічці, він може проробити кінцеву послідовність кроків, що закінчується однією з його прикінцевих конфігурацій.
Деякі види распознавателей можуть з початкової конфігурації проробити різні послідовності кроків, з яких, можливо, лише деякі (або навіть одна) приведуть до заключної конфігурації. У такому випадку вхідні ланцюжок є допущеної.
Мова, який визначається розпізнавачем - це множина всіх ланцюжків, які допускає цей распознаватель.
4.7 Види распознавателей і їх класифікація
розпізнавачів класифікують залежно від виду складових їх компонентів: зчитувального пристрою, пристрої керування і зовнішньої пам'яті.
За видами зчитувального пристрою розпізнавачі можуть бути двосторонніми і односторонніми. Односторонні розпізнавачі допускають переміщення голівки, що зчитує по стрічці тільки в одному напрямку, зазвичай зліва направо (такий распознаватель називається лівостороннім). Такі розпізнавачі не повертаються назад до вже прочитаної частини ланцюжка. Двосторонні розпізнавачі допускають переміщення голівки, що зчитує в будь-якому напрямку.
За видами пристрої керування розпізнавачі бувають детерміновані та недетермінірованние. Розпізнавач є детермінованим, якщо для будь допустимої конфігурації існує не більше однієї наступної конфігурації. Якщо для будь-якої допустимої конфігурації єдино можлива рівно один наступна конфігурація, то такий распознаватель є детермінованим повністю визначеним, інакше він неповністю певний. Для недетермінірованного распознавателя на деякому кроці, можливо, зробити кілька альтернативних переходів в різні конфігурації. При цьому може виявитися, що тільки одна з можливих послідовностей кроків приводить в заключну конфігурацію.
За видами зовнішньої пам'яті розпізнавачі бувають наступних типів:
розпізнавачі без зовнішньої пам'яті;
розпізнавачі з обмеженою зовнішньою п...
