13
$\begingroup$

While doing the current assignment for my formal languages and automata course, I kind of got stuck on exercises involving unary languages (I hope that's the right term), i.e., languages which build upon a single letter. I don't want to ask about the specific exercises, though, but rather about a much more general conjecture I've come up with:

Let $\Sigma=\{a\}$ and $L=\{a^{f(n)}\in\Sigma^*:n\in\mathbb N_0\}$. My conjecture is:
$$L\text{ is regular}\Leftrightarrow \exists x,y\in\mathbb N_0:f(n)=x\cdot n+y$$

Has this question seen any scientific treatment before? Is it "obviously" true / false?

To me, obviously the "$\Leftarrow$" direction is true because one can just construct a DFA with $x+y$ states that cycles through the $x$ states after having read through $y$ states and accepts iff it is at state number $y$.

$\endgroup$
  • $\begingroup$ Good job, making this observation is nothing I'd expect from average students! $\endgroup$ – Raphael Dec 20 '16 at 22:36
  • $\begingroup$ Agreed. This is a very nice observation. $\endgroup$ – Rick Decker Dec 20 '16 at 22:38
  • $\begingroup$ It isn't obvious from the title, but we've had this question before, up to a small equivalence lemma: What are the possible sets of word lengths in a regular language? $\endgroup$ – Gilles Nov 15 '18 at 19:01
9
$\begingroup$

Linear is close, but the technical term you're looking for is semilinear:, that is, a finite union of linear sets.

Half of the proof of this is a corollary of Parikh's Theorem, which says that any context-free language has a semi-linear Parikh map (that is, the set of vectors containing the occurrences of each letter in the alphabet).

For a unary language, the parikh map of the language is the language itself (i.e. each word is uniquely identified by how many letters it has), so every unary regular language is semi-linear.

The other half of the proof is showing that you can construct a regular language containing every unary semi-linear set. This takes a bit of work, but it's not too hard if you use regular expressions:

  • $a^k$ recognizes the language $\{ k \}$
  • $(a^k)^*$ recognizes $\{xk \mid x \in \mathbb{N}_0 \}$
  • $R_1 R_2$ recognizes $S_1 + S_2$ if $R_1$ recognizes $S_1$ and $R_2$ recognizes $S_2$, where $+$ here is element-wise addition
  • $R_1 | R_2$ recognizes $S_1 \cup S_2$ if $R_1$ recognizes $S_1$ and $R_2$ recognizes $S_2$, where $|$ here is regular-expression union.
$\endgroup$
6
$\begingroup$

You're almost correct. You need to consider the fact that you might have several linear functions, like $$ L=\{a^k\mid k=3n+1\text{ or }k=7n+4\} $$ or you might have finite languages, like $$ L=\{a^k\mid k=4n+2\text{ or }k=13\} $$ (In both cases, we're just taking the union of regular languages, so things work as they should.)

$\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.