бесконечный регулярный язык и конечное регулярное доказательство языка

Question

Предположим, что L - бесконечный регулярный язык. Следует ли из этого, что существует конечный язык S такой, что L = SS *? Докажите или опровергните, найдя контрпример.

Что я пробовал: Интуитивно это должно быть правдой. Любой бесконечный язык может быть представлен конечным языком S, если S имеет те же алфавиты, что и L, например, если L - бесконечный язык над алфавитом {a, b} *, тогда S = {a, b} работает, поэтому, по существу, S содержит только одно вхождение всех алфавитов в L. Правильно ли это или я что-то упустил? или это просто не действует вообще?

Любая помощь будет оценена!

Answer 1

Вот альтернативный контрпример, который может быть проще. Рассмотрим бесконечный регулярный язык ab *. Теперь предположим, что L = SS * для некоторого S. Теперь либо S содержит строку с символом a, либо нет. Если это так, то L = SS * содержит строки с несколькими a, поэтому он не может быть языком ab *. Если S не содержит a, тогда L = SS * не содержит строк с какими-либо a и не может быть языком ab *. В любом случае L не ab *, противоречие. Таким образом, L не может быть записано как SS * для любого S.

Answer 2

Моя интуиция заключается в том, что это неправда. Давайте возьмем пример языка всех строк нечетной длины над {a, b}. Это тривиально регулярно и тривиально бесконечно. Тем не менее, любое конечное подмножество этого языка будет иметь строки нечетной длины, а любой бесконечный суффикс должен иметь четную длину, поэтому для некоторого конечного языка S.

* 1005 не существует разумной конструкции L = SS*. * Я оставлю превращение этой интуиции в формальное доказательство для читателя.