Автоматна характеристика основних класів мов

Почнемо з більш простого класу мов – мов регулярних.

Під автоматом розуміється п’ятірка <K,X,s,q,F>, де

· K - множина станів,

· X - множина вхідних станів,

· s - функція переходів,

· qÎK - початковий стан,

· F – множина заключних станів.

Основним поняттям, на основі якого дається характеристика класів мов, є зображення мови L в автоматі A. Для того, щоб строго ввести це поняття, продовжимо функцію s на множину K´F(X), де F(X) – напівгрупа, що породжена X з одиницею e. Продовження задається індуктивно.При цій домов-леності s визначається так:

· s(k, e)=k,"kÎK (тобто кожний стан переводиться пустим словом сам в себе)

· s(k,px),pÎF(X),xÎX =>s(k,px)=s(s(k,p),x) (тобто продовження ф-ції s досить природнє.)

Будемо говорити, що мова L зображається в автоматі А <=> L={p|s(q,p)ÎF}. Автоматну характеристику класу регулярних мов дає наступна теорема:

Теорема. Мова L є регулярною <=> вона зображається в скінченому автоматі.

По аналогії з aвт. хар-кою регулярних мов, базується АХ трьох інших класів мов. Зокрема, для КВ-мов роль автоматів виконують автомати з магазинною пам’яттю, для БС-мов – лінійно-обмежені автомати, і нарешті, рекурсивно-злічені мови (як вже відомо) – машинами Тюрінга.