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