Разработать такой язык L, чтобы ни L, ни его дополнение не имели бесконечного регулярного подмножества?

Question

У меня класс по теории автоматов, и сейчас мы изучаем лемму прокачки. Есть вопрос об упражнении, задающий нам вопрос: «Разработать ли язык L так, чтобы ни L, ни его дополнение не имели бесконечного регулярного подмножества?» Но я не понимаю вопроса. Что такое бесконечное регулярное подмножество? Как мне найти язык, который может удовлетворить это требование?

Может кто-нибудь пролить свет на этот вопрос?

Спасибо!

Answer 1

Ну, бесконечное регулярное подмножество языка - это подмножество, которое бесконечно и регулярно.Хорошо, это, вероятно, не очень полезно.

Таким образом, "подмножество" довольно ясно.

"Подмножество" - это то, которое принимается детерминированным конечным автоматом (на самом деле есть удивительная теоремав теории языков, которая говорит, что это условие эквивалентно горстке других условий).

«Бесконечное множество» - это множество, которое не является конечным, или, что то же самое, множество, которое имеет бесконечно много элементов.

Итак, допустим, что язык L является особенным, если он имеет бесконечное регулярное подмножество.

Ваша задача - найти язык L такой, что оба L и дополнение кL не являются особенными.

Чтобы разобраться с этой проблемой, вам нужно сначала обдумать это определение.Возьмите несколько примеров языков из ваших заметок и вашего текста.Выясните, если они являются регулярными.Если вы обнаружите, что это не так, подумайте о том, что делает его нерегулярным, и посмотрите, разрабатываете ли вы язык, обладающий тем свойством, что все его бесконечные подмножества не являются регулярными.Затем посмотрите, что происходит, когда вы посмотрите на его дополнение.

Вы должны построить свою интуицию, и единственный способ сделать это - испачкать руки.

Answer 2

Точнее, вам нужно найти язык L, чтобы не было подмножества L, являющегося бесконечным регулярным языком, и не было подмножества дополнения к L, являющегося бесконечным регулярным языком.

Вот неправильный пример: L = объединение a^n и a^n b^n. Поскольку a^n является обычным языком и является подмножеством L, это не сработает для ответа.

Для нахождения L, который соответствует требованиям, я обнаружил, что подобные вопросы больше похожи на головоломки. Вы пробуете некоторые вещи, проверяете, работают они или нет, и пытаетесь подумать, почему они не решают проблему. В конце концов вы обдумываете ситуацию и находите решение.