| |
[Sep. 25th, 2014|11:11 am] |
Матлогику не знать стыдно.
Вот такой вопрос возник: можно ли алгоритмически распознать, является ли данный язык регулярным или контекстно-свободным?
Ну, то есть на вход алгоритма подается какая-то программа (машина Тьюринга, то есть), которая распознает данный язык.
Алгоритм говорит, какого класса этот язык. Ну и в идеале еще регулярное выражение или КС-грамматику, если есть такие.
Конечно, даже такой невежественный тип как я сразу подозревает, что ответ на этот вопрос "нет, такого алгоритма не бывает, зажрались вы, батенька".
Оказывается, есть такая теорема Райса, которая это подтверждает (и которая сама следует из какой-то матлогической теоремы о неподвижной точке).
Надо учить, да. |
|
|
