Skip to main content

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.

Filter by
Sorted by
Tagged with
27 votes
1 answer
2k views

Deciding emptiness of intersection of regular languages in subquadratic time

Let $L_1,L_2$ be two regular languages given by NFAs $M_1,M_2$ as input. Assume we would like to check whether $L_1\cap L_2\neq \emptyset$. This can clearly be done by a quadratic algorithm which ...
R B's user avatar
  • 9,458
18 votes
2 answers
840 views

Bounds on the size of the smallest NFA for L_k-distinct

Consider the language $L_{k-distinct}$ consisting of all $k$-letter strings over $\Sigma$ such that no two letters are equal: $$ L_{k-distinct} :=\{w = \sigma_1\sigma_2...\sigma_k \mid \forall i\in[k]...
R B's user avatar
  • 9,458
33 votes
5 answers
5k views

Counting words accepted by a regular grammar

Given a regular language (NFA, DFA, grammar, or regex), how can the number of accepting words in a given language be counted? Both "with exactly n letters" and "with at most n letters" are of ...
Charles's user avatar
  • 1,745
20 votes
1 answer
3k views

What is the number of languages accepted by a DFA of size $n$?

The question is simple and direct: For a fixed $n$, how many (different) languages are accepted by a DFA of size $n$ (i.e. $n$ states)? I will formally state this: Define a DFA as $(Q,\Sigma,\delta,...
Janoma's user avatar
  • 1,406
16 votes
2 answers
998 views

Regular versus TC0

According to the Complexity Zoo, $\mathsf{Reg} \subseteq \mathsf{NC^1}$ and we know that $\mathsf{Reg}$ cannot count so $\mathsf{TC^0} \not\subseteq \mathsf{Reg}$. However it doesn't say if $\mathsf{...
Kaveh's user avatar
  • 21.7k
14 votes
1 answer
3k views

minimizing size of regular expression

Suppose we have a regular language specified by a regex, for example, (ab|ac)* and we wish to find an equivalent regex with the minimal number of symbols, (a(b|c))*. Is there any efficient way to do ...
Antimony's user avatar
  • 917
13 votes
1 answer
819 views

Parameterized complexity of inclusion of regular languages

I am interested in the classic problem REGULAR LANGUAGE INCLUSION. Given a regular expression $E$, we denote by $L(E)$ the regular language associated to it. (Regular expressions are on a fixed ...
Florent Foucaud's user avatar
4 votes
1 answer
318 views

minimal finite automata given in-words and out-words

this seems an interesting FSM optimization problem; have not seen it studied, wondering if it has been and/ or looking for other insight. given: two finite sets of words $S_{in}$ and $S_{out}$. ...
vzn's user avatar
  • 11k
4 votes
3 answers
723 views

How to minimize a FSM transducer?

In contrast to FSM minimization which is well studied with various algorithms, theorems and has many practical applications, I'm looking for any nontrivial insight, analysis and references to the ...
vzn's user avatar
  • 11k
32 votes
1 answer
909 views

Eilenberg's rational hierarchy of nonrational automata & languages -- where is it now?

In the preface to his very influential books Automata, Languages and Machines (Volumes A, B), Samuel Eilenberg tantalizingly promised Volumes C and D dealing with "a hierarchy (called the rational ...
David Lewis's user avatar
23 votes
2 answers
559 views

Testing whether letters can be scheduled to achieve a word in a regular language

I fix a regular language $L$ on an alphabet $\Sigma$, and I consider the following problem that I call letter scheduling for $L$. Informally, the input gives me $n$ letters and an interval for each ...
a3nm's user avatar
  • 9,557
21 votes
2 answers
8k views

Is JSON a Regular Language?

I was wondering if the JSON spec defined a regular language. It seems simple enough, but I'm not sure how to prove it myself. The reason I ask, is because I was wondering if one could use regular ...
jjnguy's user avatar
  • 321
18 votes
3 answers
719 views

What is the minimal extension of FO that captures the class of regular languages?

Context: relations between logic and automata Büchi's Theorem states that Monadic Second Order logic over strings (MSO) captures the class of regular languages. The proof actually shows that ...
Janoma's user avatar
  • 1,406
17 votes
2 answers
808 views

How small can a NFA be, compared to the minimal Unambiguous Finite Automaton (UFA) of the same regular language?

Unambiguous Finite Automatons (UFA) are special type of non-deterministic finite automatons (NFA). A NFA is called unambiguous if every word $w\in \Sigma^*$ has at most one accepting path. This ...
R B's user avatar
  • 9,458
14 votes
3 answers
1k views

The significance of state complexity in automata and regular languages?

I'm reading "Concatenation of Regular Languages and Descriptional Complexity" by Galina Jiraskova, 2009 on the state complexity resulting from concatenation of two regular languages ( by Galina ...
Airmine's user avatar
  • 143
11 votes
1 answer
177 views

Check whether DFA accepts majority of words less than a cutoff with another DFA

Question Let $M$ be some DFA that reads integers in base $k$. Does there always exist some other DFA $M'$ that also reads integers in base $k$, where $M'(x)$ accepts if and only if $M$ accepts the ...
Jake's user avatar
  • 1,214
11 votes
2 answers
296 views

Is there a simple characterization of regular languages closed under circular shifts?

A language $L$ is closed under circular shifts if, for every word $w = a_1 ... a_n$ and circular shift $w' = a_i ... a_n a_1 ... a_{i-1}$ of $w$, then $w \in L$ iff $w' \in L$. It is equivalent to ...
a3nm's user avatar
  • 9,557
10 votes
1 answer
356 views

The complexity of conversion from a regular expression to a nondeterminsitic automata and back after changing initial and final states

Suppose that a regular expression $\mathcal{R}$ over an alphabet $\Sigma$ is given. It is well-known that one can now construct a non-deterministic finite automaton $\mathcal{A}$ such that $\mathcal{R}...
Bartosz Bednarczyk's user avatar
10 votes
1 answer
265 views

Is it decidable whether the output length of a transducer is bounded by the input length?

The transducers considered here are those Wikipedia calls finite state transducers. The behavior of a transducer $T$, that is, the relation it computes, is written $[T]$: a word $y$ is an output for $...
vzn's user avatar
  • 11k
8 votes
1 answer
368 views

Converting 2-ambiguous NFA to unambiguous NFA

This must be known, but somehow I can't locate a reference about this. Let $A$ be a nondeterministic finite automaton (NFA) over words of an alphabet $\Sigma$. I say that $A$ is unambigous if, for ...
a3nm's user avatar
  • 9,557
7 votes
1 answer
641 views

On the relation for the Myhill-Nerode theorem/syntactic monoid of a language

In order to characterize regular languages one finds the following definition useful: Let $\Sigma$ be an alphabet and $L\subseteq\Sigma^*$. Say that $x,y\in\Sigma^*$ are $\equiv_L$-related, and ...
Janoma's user avatar
  • 1,406
6 votes
2 answers
302 views

Generating all instances of a regular language up to a certain length

Given a fixed regular language R, what is the complexity of generating all members of R with length at most $n$? Suppose some reasonable model (RAM with $n$-bit words?) and a write-only output tape. ...
Charles's user avatar
  • 1,745
6 votes
7 answers
2k views

What are regular expressions good for?

If you ask a question about parsing HTML with regex, you will certainly be referenced to this famous rant. Though there is not a canonical rant for it, I've also been told that regex aren't powerful ...
Eric Wilson's user avatar
5 votes
2 answers
223 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 ...
Bartosz Bednarczyk's user avatar
4 votes
1 answer
282 views

Getting an automaton from set of words in and out of a language [duplicate]

Possible Duplicate: Is finding the minimum regular expression an NP-complete problem? Let's suppose that I have an unknown language $\mathcal L$, I know only two (particularly large) sets of ...
yo''s user avatar
  • 141
3 votes
1 answer
236 views

Finding self-similar homomorphisms of a FSM transducer

Consider a special case of homomorphisms of FSM transducers (or "generalized sequential machines" in [1]). Let $F$ be a transducer accepting a language $L$, and let $h(x)$ be a homomorphism function ...
vzn's user avatar
  • 11k
3 votes
3 answers
168 views

Example of monoid $M$ such that $\operatorname{RAT}(M) \not\subseteq \operatorname{REC}(M)$

Let $M$ be a monoid, the family of rational sets $\operatorname{RAT}(M)$ is defined as the smallest set containing the finite subsets, and closed under union, concatentaion and the star operation. The ...
StefanH's user avatar
  • 2,077
2 votes
1 answer
256 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$ ...
Turbo's user avatar
  • 13k
0 votes
0 answers
69 views

How to reduce a code down to its configuration

I have built a system where from atomic information of a UI code I could generate a framework specific code. Here is the concept https://github.com/imvetri/ui-editor. For example, the user of this ...
Vetrivel's user avatar