# Questions tagged [regular-language]

Questions about the formal languages that can be described by regular expressions (in the sense of Kleene), or, equivalently, the languages that can be accepted by finite automata.

119 questions
Filter by
Sorted by
Tagged with
1answer
110 views

### Reference request: An algebraic characterisation of LTL[XF]-definable word languages

I'm looking for a reference to the fact that LTL[XF]-definable languages (LTL where only the (strict) finally/future modality is allowed) correspond to the variety $\mathbf{R}$ (see: 1). A similar ...
3answers
3k views

### Regular languages from category-theoretical point of view

I noticed that regular languages over the alphabet $\Sigma$ can be naturally thought of as a poset, and indeed a lattice. Moreover, concatenation together with the empty language $\epsilon$ defines a ...
1answer
154 views

### Is the function $f(a_1 \dotsm a_n) = a_1(a_1a_2)(a_1a_2a_3)\ \dotsm\ (a_1 \dotsm a_n)$ regularity-preserving?

A function $f: A^* \to A^*$ is regularity-preserving if, for each regular language $L$ of $A^*$, the language $f^{-1}(L)$ is regular. I think I have a proof, as a consequence of more general results, ...
0answers
63 views

### Necessary and sufficient condition for an infinite tree to be context-free

A Buchi automaton is non-empty iff it accepts an infinite word of the form $uv^\omega$ (here $u,v$ are finite words). In other words, if $\{w\}$ is an $\omega$-regular language, then it is of that ...
1answer
132 views

### DFSA and NFSA intersection problem

Given $k$ deterministic FSAs of $n$ states the intersection of their languages is empty is decidable in $n^{o(k)}$ time is an open problem. For unbounded $k$ it is known the problem is $PSPACE$ ...
1answer
88 views

### NP-Completeness of Finding Minimum Automaton, in Gold's paper

I have been investigating "learning automatas", and I came across reference to Gold's papers several times: "Complexity Of Automaton Identification From Given Data", and "...
1answer
107 views

1answer
421 views

### What class of languages is recognized by finite-state automata with $k$ heads?

A DFA or NFA reads through an input string with a single head, moving left-to-right. It seems natural to wonder about finite-state machines that have multiple heads, each of which moves through the ...
0answers
289 views

2answers
690 views

1answer
90 views

### Prove that L* is a regular language [closed]

Suppose that L is any language , not necessarily regular, whose alphabet is {0}; that is the strings of L consist of 0's only. Prove that L* is regular.
1answer
236 views

### Existence of an algorithm

I need to show that there exists a polynomial time algorithm that inputs a deterministic automata $A$, and decides if $A$ accepts a word w if and only if it also accepts any word obtained by permuting ...
1answer
216 views