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