Questions tagged [automata-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
11 votes
5 answers
2k views

Generating function of a regular language

It is well known that the generating function of a regular language $L$, i.e. $\sum n_kz^k$ where $n_k$ is the number of words of length $k$ in $L$, is rational, i.e. a quotient of two polynomials $P(...
user avatar
5 votes
1 answer
280 views

Is it decidable whether the support of a rational $\mathbb{Z}$-series is a regular language?

Let $S \in \mathbb{Z}\langle\langle A\rangle\rangle$ be a rational series in noncommutative variables. The support of $S$ is the set of all words $u \in A^*$ such that $(S, u) \not= 0$. It is ...
user avatar
  • 781
3 votes
3 answers
526 views

Finite variation and idempotent languages and automata

Let $L$ be a regular language over alphabet $\Sigma$ and let $A:=(Q,\Sigma,\delta, q_0, F)$ be the minimal DFA recognizing $L$. For every $w\in \Sigma^*$ define the variation of $w$ w.r.t. $L$ by $$\...
user avatar
  • 434
2 votes
1 answer
809 views

Proof that the $\omega$-language consisting of all words containing every finite word as a factor is not rational/regular

Let $\eta$ be an $\omega$-word over $X = \{0,1\}$ and let $F_k(\eta)$ denote the factors of $\eta$ of length $k$. Define the following $\omega$-languages $$ L_k := \{ \xi : F_k(\xi) = X^k \} = \{ \xi ...
user avatar
  • 693