Регулярні мови і граматики
Нехай заданий кінцевий алфавіт
і тим самим безліч всіх кінцевих слів в цьому алфавіті:
.
Формальна мова в алфавіті - це довільна підмножина.
Набір правил творення слів формального мови називають його граматикою. Залежно від складності цих правил формальні мови діляться на ряд класів. Далі ми розглянемо один з найбільш простих класів мов - регулярні мови - і встановимо їх зв'язок з кінцевими автоматами.
Розглянемо сукупність мов з одним і тим же алфавітом і введемо операції над цими мовами.
1 °. Об'єднання. Це теоретико-множинна операція, яка, на відміну від перетину і доповнення, має природну синтаксичну інтерпретацію:
.
2 °. Конкатенація - це операція, пов'язана з підстановкою мови в мову:
.
3 °. Ітерація мови визначається рівністю
,
де - мова, що складається з порожнього слова, який не треба змішувати з порожнім мовою. що не містить жодного слова; . . ...
Мови. . що складаються з порожнього або однобуквеним слова, називаються елементарними.
Мова називається регулярним. якщо його можна побудувати за допомогою кінцевого числа операцій об'єднання, конкатенації і ітерації.
35. Кінцевий автомат називається автоматом Мура. якщо його функція виходів залежить тільки від стану:
.
Загальна модель кінцевого автомата, яка розглядалася раніше, називається автоматом Міллі.
Незважаючи на те, що автомат Міллі - окремий випадок автомата Мура, можливості цих двох автоматів збігаються.
Теорема. Для будь-якого автомата Міллі існує еквівалентний йому автомат Мура.
Розглянемо автомат Мура з двома вихідними символами 0 і 1.Таким автомат буде для одних вхідних слів видавати 1, для інших - 0. Будемо вважати, що в першому випадку автомат «розпізнав» слово, а в другому - немає. Тим самим визначається деякий мову, що складається зі слів, які розпізнаються автоматично.
Розіб'ємо стану автомата Мура на два класи: клас - вихід дорівнює 1, клас - вихід дорівнює 0. Це дозволяє не розглядати функцію виходів і визначити автомат-распознаватель як систему
.
З кожним таким автоматом зв'яжемо розпізнається їм мову
,
тобто мова складається з усіх слів, які переводять автомат з початкового стану в одне з останніх.
Приклад. . де. . . . а задається таблицею