Interesting formal languages proof.

92 Views Asked by At

I found this exercise (9.14) in chapter 9 of the book "Dynamic Logic" by Harel, Kozen and Tiuryn. I have absolutely no clue how to provide a proof for the exercise.

Prove that for any language $L$ over alphabet $\{a\}$ and any infinite regular language $\alpha$ over alphabet $\{a\}$, the concatenation language $L\alpha$ is regular.

Especially what happens when $L$ is language of all words over alphabet $\{a\}$ which lengths are of prime numbers.

1

There are 1 best solutions below

4
On BEST ANSWER

This is unfortunately not true. Take $L = \{a^p \mid \text{$p$ is an odd prime} \}$ and let $K = 1 + a(a^2)^*$. The language $K$ is infinite and regular. Moreover, since $L$ is a subset of $a(a^2)^*$, one gets $$ La(a^2)^* \subseteq a(a^2)^*a(a^2)^* \subseteq (a^2)^*. $$ Suppose that $LK$ is regular. Then $LK \cap a(a^2)^*$ would also be regular. But $$ LK = L(1 + a(a^2)^*) = L + La(a^2)^* $$ and hence $LK \cap a(a^2)^* = L$, which is not regular. Contradiction.