Формальный язык

представимый машиной", " формальный язык, распознаваемый машиной,- множество всех тех слов, при работе над к-рыми машина попадает в одно из выделенных состояний. Всякое рекурсивно перечислимое множество слов есть формальный язык (ф. я.), представимый нек-рой Тьюринга машиной. Чаще всего рассматривают распознавание машинами рекурсивных ф. я. Так, регулярные языки и только они распознаются автоматами конечными;контекстно-свободные языки и только они распознаются автоматами с магазинной памятью. В том случае, когда ф. я. состоит из бесконечных слов (сверхслов), он наз. сверхъязыком. Определение распознавания сверхъязыка на машине может отличаться от основного определения. Напр., слово. принадлежит сверхъязыку, распознаваемому конечным автоматом [img: http://localhost:8080/file/052208-71.jpg] тогда и только тогда, когда при работе над словом хавтомат [img: http://localhost:8080/file/052208-72.jpg] бесконечное число раз попадает в выделенное подмножество состояний. При изучении конкретных ф. я., заданных не в машинных терминах (напр., посредством формальных грамматик), часто возникает потребность пек-рым образом охарактеризовать сложность языка. Одним из наиболее распространенных путей в зтом направлении является отыскание подходящего класса машин, распознающих рассматриваемые языки, и определение сложности языков через сложностные характеристики машин. С другой стороны, изучение конкретного класса машин, как правило, включает описание Ф. я., п. м. этого класса. Дальнейшее исследование Ф. я., п. м. затрагивает вопросы соотношения с известными классами языков, свойства замкнутости (относительно теоретико-множественных операций и т. п.), вопросы алгоритмического и сложностного характеров.