Если регулярный язык содержит только звезду Клини, то возможно ли, что это происходит от объединения двух нерегулярных языков?

Question

Я хочу знать, что при заданном обычном языке L, который содержит только оператор звезды Клини (например, (ab)*), возможно ли, что L можно сгенерировать путем конкатенации двух нерегулярных языков? Я пытаюсь доказать, что L может быть сгенерирован только путем объединения двух обычных языков.

Благодарю.

Answer 1

Это утверждение неверно. Рассмотрим эти два языка над Σ = {a}:

L₁ = {aⁿ | n является степенью двойки} ∪ { ε }

L₂ = {aⁿ | n не является степенью двойки} ∪ { ε }

Ни один из этих языков не является регулярным (первый может быть доказан нерегулярным с помощью теоремы Майхилла-Нерода, а второй тесно связан с дополнением к L₁ и также может быть доказан нерегулярным.

Тем не менее, я собираюсь утверждать, что L₁ L₂ = a*. Во-первых, обратите внимание, что любая строка в конкатенации L₁ L₂ имеет форму aⁿ и, следовательно, является элементом a*. Далее возьмите любую строку в *; пусть это будет^п. Если n является степенью двойки, то она может быть сформирована как конкатенация aⁿ из L₁ и ε из L₂. В противном случае n не является степенью двойки, и его можно сформировать как конкатенацию ε из L₁ и aⁿ из L₂. Следовательно, L_1, L₂ = a *, поэтому теорема, которую вы пытаетесь доказать, неверна.

Надеюсь это поможет!