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

Question

Я хотел бы знать, если конкатенация между двумя языками (один обычный, а другой нет) всегда не является регулярной, или может случиться так, что вывод является обычным языком. Благодарю.

Answer 1

Нет, потому что мы можем найти контрпример, который доказывает, что иногда это случается:

L1 не регулярный: (a^2)^n с n> 1
L2 регулярный: a*

Конкатенация создает язык L3= aa*, и это, очевидно, регулярно.

Answer 2

a^(2^n) n>=0 не является регулярным, за исключением того, что конкатенация с * все еще не является регулярной. Это становится L = {a^(2^n)a*, n>=0}, который в основном сводится к L={aa*}, который является регулярным.

Patrick87, (a ^ 2) ^ nn> 1 имеет регулярное выражение (aaaa)(aa)*

Answer 3

Помните, что пустой язык ∅ и одноэлементный язык пустой строки {ε} являются обычными. Конкатенация любого нерегулярного языка и пустого языка является пустым языком (регулярным), а конкатенация любого нерегулярного языка и {ε} является исходным языком (нерегулярным). Поэтому ответ зависит от выбора языков.

(@Hyruma92 дает еще один пример того, где конкатенация дает регулярный язык; я добавил этот ответ, потому что я думаю, что он более прямолинейный и просто приводит вас к этому. Здесь интуиция заключается в том, что пустой язык является нулевым элементом для языковой конкатенации и {ε} это элемент идентичности, который мотивирует вас попробовать их.)