1
$\begingroup$

Give an algorithm that, given an NFA over a one-letter alphabet, determines whether the language it generates has the property that for some $n$, $$ L^* = \bigcup_{k=0}^n L^k. $$

I need some tips how to solve that.

$\endgroup$
  • $\begingroup$ What is $L$? Should it be $L^k$ (without braces) instead of $\{L^k\}$? $\endgroup$ – xskxzr May 18 '18 at 18:06
1
$\begingroup$

We can identify every unary regular language $L$ with the set $S = \{ n : 1^n \in L \}$. It is known that $S$ is eventually periodic, that is, $$ S = A \cup (B + m \mathbb{N}) = A \cup \{ b + mn : b \in B, n \in \mathbb{N} \} $$ for some finite $A,B$ and $m \geq 1$. Let us consider four cases:

Case 1. $S$ is empty. In this case, $S^* = S^0$.

Case 2. $S$ is finite and non-empty. In this case, $S^*$ is infinite but $S^0 \cup \dots \cup S^n$ is finite for all $n$.

Case 3. $S = B + m\mathbb{N}$ for some non-empty $B$ and $m \geq 1$. I claim that $$ B^* \bmod{m} = (B^1 \cup \dots \cup B^\ell) \bmod{m} $$ for some finite $\ell$. Indeed, if $i \in B^* \bmod{m}$ then $i \in B^j \bmod{m}$ by definition of $B^*$ for some $j \geq 1$ (when $i = 0$ we can take $j = m$), so we can take $\ell$ to be the maximum of the $j$'s. It follows that $$ S^+ = \bigcup_{i \in B^* \bmod m} n_i + m \mathbb{N}, \text{ where } n_i \equiv i \pmod{m}, \\ S^1 \cup \cdots \cup S^\ell = \bigcup_{i \in B^* \bmod m} n'_i + m \mathbb{N}, \text{ where } n_i \equiv i \pmod{m}, $$ where $n'_i \geq n_i$. It follows that $S^* \setminus (S^0 \cup \cdots \cup S^\ell)$ is finite, and so $S^* = S^0 \cup \cdots \cup S^r$ for some finite $r \geq \ell$, since every element in $S^* \setminus (S^0 \cup \cdots \cup S^\ell)$ appears in some $S^j$.

Case 4. $S = A \cup (B+m \mathbb{N})$ for some non-empty $A,B$ and $m \geq 1$. Let $C = A \cup B$. As before, $$ C^* \bmod m = (C^0 \cup \cdots \cup C^\ell) \bmod m $$ for some finite $\ell$. Since $B$ is non-empty, $(B+m \mathbb{N})^m$ contains some multiple of $m$, and so all large enough multiples of $m$. Assuming $\ell \geq m$, it follows that $$ S^* = D \cup \bigcup_{i \in C^* \bmod m} n_i + m \mathbb{N}, \text{ where } n_i \equiv i \pmod{m}, \\ S^0 \cup \cdots \cup S^\ell = D' \cup \bigcup_{i \in C^* \bmod m} n'_i + m \mathbb{N}, \text{ where } n_i \equiv i \pmod{m}, $$ where $D \supseteq D'$ are finite and $n'_i \geq n_i$. It follows that $S^* \setminus (S^0 \cup \cdots \cup S^\ell)$ is finite, and so $S^* = S^0 \cup \cdots \cup S^r$ for some finite $r \geq \ell$.

Conclusion. The property $S^* = S^0 \cup \cdots \cup S^n$ holds for some finite $n$ unless $S$ is finite and non-empty. Given a finite automaton for $L$, this condition is easy to check (in linear time).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.