Regular languages of finite index

Ex from Shallit. Let L\subseteq \Sigma^* be a language. If k\geq 1 is s.t. L^{k-1}\neq L^{k}=L^{k+1} say that L has finite index equal to k. Then for every k\geq 1 there exists a regular language of finite index equal to k.

Proof. Fix k\geq 1 and pick \Sigma such that |\Sigma| = k.
Let L_{\leq 1}\subseteq \Sigma^* be the language of words containing at most one distinct letter in \Sigma. This is a regular language. Then L^i=L_{\leq i} is the language of words containing at most i distinct letters in \Sigma. Since |\Sigma|=k one has that L^{i-1} \neq L^i \neq L^{i+1} for every 1 < i < k but L^{k}=L^{k+1}. Q.E.D.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s