Я хочу знать, что для обычного языка L, который содержит только звездный оператор Клини (например, (ab)*), возможно ли, что L может быть сгенерирован конкатенацией двух нерегулярных языков? Я пытаюсь доказать, что L может быть получен только конкатенацией двух обычных языков.
Спасибо.
Это утверждение неверно. Рассмотрим эти два языка над = {a}:
L1 = { an | n является степенью двойки } { }
L2 = { an | n не является степенью двойки } { }
Ни один из этих языков не является регулярным (нерегулярность первого можно доказать с помощью теоремы Майхилла-Нероде, а второй тесно связан с дополнением L1 и также может быть доказано, что он является нерегулярный.
Однако я собираюсь заявить, что L1L2 = a*. Во-первых, обратите внимание, что любая строка в конкатенации L1L2 имеет вид an и, следовательно, является элементом a*. Затем возьмите любую строку из a*; пусть это будет n. Если n является степенью двойки, то оно может быть сформировано как конкатенация an из L1 и из L2. В противном случае n не является степенью двойки и может быть сформировано как конкатенация из L1 и an из L2 . Следовательно, L1L2 = a*, поэтому теорема, которую вы пытаетесь доказать, неверна.
Надеюсь это поможет!
