Power of a group of languages

35 Views Asked by At

I need help finding and proving the power of the group of languages A:

A={L|L=L* and L is over $\Sigma\ = \{1\}\ $}

I was thinking of the fact that if L=L* - if $1^k\ ,1^p \in L $ then,

m=k+p , $1^m \in L\\$

but im not sure how to continue from here, thank you in advance:)

1

There are 1 best solutions below

2
On

Yes, basically that's all that could be said:

Given a language $L$ on alphabet $\{1\}$, and let $N_L:=\{n:1^n\in L\}$, then we have $N_{L^*}$ is the submonoid of $(\Bbb N,+,0)$ generated by $N_L$, so that $L=L^*$ iff $N_L$ is already a submonoid, that is, if it contains $0$ and is closed under addition, (i.e. $L$ contains the empty word and is closed under concatenation - including repetition).

Based on e.g. this question, we conclude that every submonoid of $\Bbb N$ is finitely generated, and consequently, $L=L^*$ iff $L=(w_1|w_2|\dots|w_k)^*$ for some words $w_i\in 1^*$.