Математическая энциклопедия - формальный язык представимый машиной
Связанные словари
Формальный язык представимый машиной
формальный язык, распознаваемый машиной,множество всех тех слов, при работе над к-рыми машина попадает в одно из выделенных состояний. Всякое рекурсивно перечислимое множество слов есть формальный язык (ф. я.), представимый нек-рой Тьюринга машиной. Чаще всего рассматривают распознавание машинами рекурсивных ф. я. Так, регулярные языки и только они распознаются автоматами конечными;контекстно-свободные языки и только они распознаются автоматами с магазинной памятью.
В том случае, когда ф. я. состоит из бесконечных слов (сверхслов), он наз. сверхъязыком. Определение распознавания сверхъязыка на машине может отличаться от основного определения. Напр., слово . принадлежит сверхъязыку, распознаваемому конечным автоматом тогда и только тогда, когда при работе над словом хавтомат бесконечное число раз попадает в выделенное подмножество состояний.
При изучении конкретных ф. я., заданных не в машинных терминах (напр., посредством формальных грамматик), часто возникает потребность пек-рым образом охарактеризовать сложность языка. Одним из наиболее распространенных путей в зтом направлении является отыскание подходящего класса машин, распознающих рассматриваемые языки, и определение сложности языков через сложностные характеристики машин. С другой стороны, изучение конкретного класса машин, как правило, включает описание Ф. я., п. м. этого класса. Дальнейшее исследование Ф. я., п. м. затрагивает вопросы соотношения с известными классами языков, свойства замкнутости (относительно теоретико-множественных операций и т. п.), вопросы алгоритмического и сложностного характеров.
Лит.:[1] Языки и автоматы. Сб. переводов, М., 1975.
С. С. Марченков.
Математическая энциклопедия. — М.: Советская энциклопедия
И. М. Виноградов
1977—1985
Вопрос-ответ:
Похожие слова
Самые популярные термины
1 | 558 | |
2 | 484 | |
3 | 482 | |
4 | 473 | |
5 | 455 | |
6 | 441 | |
7 | 437 | |
8 | 434 | |
9 | 425 | |
10 | 425 | |
11 | 423 | |
12 | 413 | |
13 | 407 | |
14 | 376 | |
15 | 375 | |
16 | 373 | |
17 | 366 | |
18 | 365 | |
19 | 365 | |
20 | 362 |