Скінченні автомати.

У даній лекції розглядаються два найбільш поширених способи визначення формальних мов: граматики та автомати. Розглядаються скінченні автомати, що відповідають у ієрархії Хомського праволінійним граматикам, визначаються поняття скінченного автомату, недетермінованого скінченного автомату і мови, що розпізнається скінченним автоматом. Наведено практичні приклади і вправи для закріплення матеріалу

Два найбільш поширених способи задання формальної мови - це граматики й автомати. Автоматами в даному контексті називають математичні моделі деяких обчислювальних пристроїв. В цій лекції розглядаються скінченні автомати, що відповідають у ієрархії Хомського праволінійним граматикам. Термін "автоматна мова" закріплений за мовами, що розпізнається саме скінченними автоматами, а не якимись більш широкими родинами автоматів (наприклад, автоматами з магазинною пам'яттю або лінійно обмеженими автоматами).

У розділі 2.1 визначаються поняття скінченного автомату (для ясності такий автомат можна називати недетермінованим скінченним автоматом) і мови, що розпізнається скінченним автоматом . У наступному розділі дається інше, але еквівалентне першому визначення мови, що розпізнається скінченним автоматом. Воно не є необхідним для подальшого викладу, але саме це визначення піддається узагальненню на випадки автоматів інших типів.

У розділі 2.3 доводиться, що той же клас автоматних мов можна отримати, використовуючи лише скінченні автомати спеціального виду (вони читають на кожному такті рівно один символ і мають рівно один початковий стан). У багатьох підручниках скінченними автоматами називають саме такі автомати.

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

Інша серія результатів пов'язана з можливістю звузити певний клас граматик, не змінивши при цьому клас породжуваних ними мов. Зазвичай у такому випадку граматики з меншого класу називаються граматиками в нормальній формі. У розділі 2.5 * формулюється результат такого типу для праволінійних граматик. Сама ця теорема не представляє великого інтересу, але аналогічні результати, які доводяться пізніше для контекстно-вільних граматик, використовуються в багатьох доведеннях та алгоритмах.

Не всі скінченні автомати підходять для конструювання розпізнавальних пристроїв, придатних для практичної реалізації, тому що в загальному випадку скінченний автомат не дає точної вказівки, як поступати на черговому кроці , а дозволяє продовжувати обчислювальний процес декількома способами. Цього недоліку немає у детермінованих скінченних автоматів (часткового випадку недетермінованих скінченних автоматів), визначених у розділі 2.6. У розділі 2.7 доводиться, що кожна автоматна мова задається деяким детермінованим скінченним автоматом.