У каждого ли обычного языка есть правильный регулярный суперсет? или собственно
Подмножество
Для фиксированного алфавита нет: существует по крайней мере один обычный язык, для которого нет правильного правильного подмножества, и по крайней мере один обычный язык, для которого нет правильного правильного подмножества.
Подсказка1: определение этих языков невероятно простое, так что каждый из них может быть полностью описан не более чем пятью и тремя словами (два и одно, если вы пропустите статьи, предлоги, «язык» и «строки») .
Подсказка2: тот факт, что вы говорите о регулярности и языках вместо какого-либо свойства для какого-либо набора, не очень важен для ответа на этот вопрос. Все, что важно, это то, что для фиксированного алфавита наборы с этим свойством включают в себя два очень важных набора, которые при идентификации отвечают на этот вопрос.