Is the language containing a single infinite length string regular?

219 Views Asked by At

I am trying to prove that every finite language is regular. I have come up with a proof that every language with a finite number of finite length strings is regular (shown at the bottom of this post), but now I am looking to prove the claim for languages with a finite number of finite or infinte length strings.

If I can show that any language containing a single string is regular, then the claim follows from the closure of regular languages under set union. It is easy to show that any language containing a single string of finite length is regular using the fact that individual characters are regular combined with the closure of regular languages under concatenation. But how do I do this for a infinite length string?

It appears that I cannot simply use closure under concatenation because this is defined as a finite closure. I am under the impression that if $\cdot$ is some operation on the elements of set $S$, and $S$ is closed in the sense that $x\cdot y\in S$ for any $x,y\in S$, the principal of mathematical induction says that $x_1\cdot x_2\cdot...\cdot x_n\in S$ for $x_i\in S$ and any $n\in\mathbb{N}$, but combining a countably infinite number of elements in $S$ using $\cdot$ is not necessarily closed because $\infty\notin\mathbb{N}$. Is this true?

If so, how else could one prove that a language containing a single infinite string is regular?

My original proof for finite strings is shown below (not really important for question, so don't read it if you don't want to):

Let $\Sigma=\{1,...,n\}$. Consider the language $L$ such that $|L|<\infty$. We can enumerate $L=\{w_1,...,w_m\}$. Construct the NFA $X=(\Sigma, Q, q_0,\delta,F)$. If $\varepsilon\in L$, then include an epsilon transition from $q_0$ into accept state $q_\varepsilon\in F$. Now, for each nonempty $w_i=x_1x_2...x_k\in L$, define the state $q_{i,1}$ such that $q_{i.1}\in\delta(q_0,x_1)$. Then, define the sequence of states $q_{i,2},q_{i,3},...,q_{i,k}$ where $q_{i,j}$ transitions into the state $q_{i,j+1}$ given input character $x_{j+1}$ for $j\in[k-1]$, and where $q_{i,j}$ implicitly rejects any other character. Then, letting $q_{i,k}\in F$, we see that the sequence of states $q_0,q_{i,2},q_{i,3},...,q_{i,k}$ accepts the string $w_i$. Since we have defined such a branch $q_0,q_{i,2},q_{i,3},...,q_{i,k}$ for all $i\in[m]$, every $w_i\in L$ is accepted by $X$. Furthermore, Each branch $q_0,q_{i,2},q_{i,3},...,q_{i,k}$ does not accept any string $w$ that is not equal to $w_i\in L$, so it follows that every string $w\notin L$ will be rejected by $X$. Thus, $X$ decides $L$, which proves that $L$ is regular.