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
5 votes
2 answers
201 views

The empty tree-word for regular tree languages

Are there references that consider the "empty tree-word" as an allowable element of regular languages of trees? Are there situations where it is more sensible to allow an empty tree-word? ...
TomKern's user avatar
  • 489
4 votes
0 answers
135 views

Learning a regular language with a specified closure property

Consider an alphabet $\Sigma$, and a partial transformation function $f:S\to\Sigma^\ast$ defined on some subset $S\subseteq\Sigma^\ast$. Let $S_f$ denote the set of strings $s\in S$ such that $f^n(s)\...
LegionMammal978's user avatar
10 votes
5 answers
304 views

Obscure characterizations of the regular languages

I've been collecting equivalent characterizations of the regular languages. Does anyone know of any I haven't yet found? Wikipedia has a bunch: https://en.wikipedia.org/wiki/Regular_language#...
TomKern's user avatar
  • 489
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,527
3 votes
1 answer
176 views

Is it useful to "untangle" an NFA by converting to a regular expression and back

Consider the following recursive algorithm for converting a regular expression into a transition diagram for an NFA with epsilon-edges (freely, optionally traversible edges), one start state and one ...
TomKern's user avatar
  • 489
0 votes
1 answer
86 views

What is the intution on the TTT algorithm for regular grammar inference?

This question is about the TTT algorithm for blackbox automata inference as defined in [1] and [2]. I am finding it difficult to understand all the innovations made by the algorithm. I understand how ...
Rahul Gopinath's user avatar
2 votes
1 answer
116 views

What is the current state of the art on exact identification of DFAs with a maximum N states

This is a question about the blackbox grammar inference of deterministic finite state automata (DFAs). In particular I want to ask about when one can exactly identify the target DFA using queries to ...
Rahul Gopinath's user avatar
7 votes
1 answer
254 views

Are regular expressions polynomially decomposable?

This question is related to my previous question (LINK). I would like to ask whether regular expressions can be polynomially decomposed in the following sense: A regular expression $\mathcal{R}$ is $...
Bartosz Bednarczyk's user avatar
10 votes
1 answer
352 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
6 votes
0 answers
76 views

Updating (minimal) DFA incrementally

Is there algorithm to incrementally update (minimal) DFA? Namely, having relatively large minimized DFA I want to update it incrementally using union and sudtraction with other (relatively small, ...
gsv's user avatar
  • 421
0 votes
0 answers
68 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
7 votes
1 answer
161 views

Complexity of the inevitability problem over monoids

I am interested in the complexity of following problem: Inevitability problem in monoids Input: two regular languages $K$, $L$ specified by finite monoids $M_K$ and $M_L$ (+ morphisms and accepting ...
Rémi's user avatar
  • 262
8 votes
1 answer
364 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,527
1 vote
0 answers
37 views

Overlap operator for simple ( regex-like ) Patterns

( Introduction ) Some Notation lower case letters, $a, b, c$ will be used to denote single symbols Upper case letters, $P, Q, R$ will be used to denote string of symbols $a\!:\!S$ means a string ...
Sam Coutteau's user avatar
2 votes
0 answers
74 views

Languages free of concatenations of stars

Union-free regular languages, defined by regular expressions (using $*$, literals (alphabet symbols), and concatenation) excluding union (written $+$ or $\cup$) have been studied. Note that unions ...
Bjørn Kjos-Hanssen's user avatar
3 votes
1 answer
145 views

What is the solution of this equation on regular languages?

I need to characterize this language: $$ L = \{ s \in \Sigma^* \, | \, \{s\} \cdot A_1 \subseteq B_1 \land \ldots \land \{s\} \cdot A_n \subseteq B_n \} $$ where $A_i, B_i$ are all regular languages. ...
Pietro Braione's user avatar
5 votes
1 answer
118 views

Logical Equivalents of Finite State Transducers

There's a notion of "regular" function on words in automata theory that corresponds nicely to functions in WS1S/Büchi Arithmetic/the logic of words with a prefix and equal-length relation. ...
TomKern's user avatar
  • 489
9 votes
2 answers
290 views

Defining regular language classes with disjoint union

Regular languages are typically defined using the operations of union, concatenation, and Kleene star. Likewise, there are restricted classes of regular languages defined via similar operations, for ...
a3nm's user avatar
  • 9,527
4 votes
1 answer
180 views

Subset of regular languages

I have a system that is deciding a subset of regular languages and am curious if anyone has seen this type before and if it has a name I could use to research more. Specifically consider the ...
sligocki's user avatar
  • 302
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
4 votes
0 answers
58 views

Reference for cost of translating between regular language formalisms

It is well-known that regular languages can be defined equivalently via many formalisms, among which regular expressions, NFAs, finite monoids, Monadic Second-Order logic (MSO). The cost (say in size ...
Denis's user avatar
  • 8,903
11 votes
1 answer
290 views

Existence of injective length-preserving rational function to a smaller alphabet

(This is a simpler rephrasing of an earlier question I have since deleted.) Definitions For this question, a finite-state transducer is like a standard NFA, except at each transition, the transducer ...
Jake's user avatar
  • 1,214
0 votes
0 answers
46 views

Capturing a particular regular language with $O(m)$ states

In dx.doi.org/10.1006/inco.2001.3069 the authors defined $NID_m = \{ u\in \{0,1\}^* | \exists i : u_i \neq u_{i + m} \}$ and claimed it could be recognized by a NFA of size $O(m)$. The paper mentions ...
Alex Williams's user avatar
6 votes
1 answer
215 views

star height of star-free languages

I'm interested in the (restricted) star-height of star free-languages. Recalling the definitions: the star height $h(\mathtt{e})$ of a regular expression $\mathtt{e}$ is $0$ if $\mathtt{e}= \...
thibo's user avatar
  • 193
5 votes
1 answer
191 views

Regular Expressions that converts into unambiguous automata

Brüggemann-Klein and Wood (1992) proved that a certain kind of regular expressions, that they call “Deterministic Regular expressions”, when converted into automata using the Glushkov's Construction, ...
ricardorr's user avatar
  • 561
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
6 votes
1 answer
187 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, ...
J.-E. Pin's user avatar
  • 4,841
2 votes
0 answers
104 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 ...
Faustus's user avatar
  • 193
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
2 votes
1 answer
195 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 "...
Makketronix's user avatar
-1 votes
1 answer
514 views

What is the time complexity of computing intersection and union of Nondeterministic Finite Automata (NFAs)?

Assume that $\mathcal{A} = (Q_A, \Sigma, \Delta_A, q_{i_A}, F_A)$ and $\mathcal{B} = (Q_B, \Sigma, \Delta_B, q_{i_B}, F_B)$ are two NFAs. What is the worst-case time complexity of computing $\mathcal{...
greps's user avatar
  • 157
5 votes
1 answer
105 views

Nonterminal descriptional complexity of regular languages

Recently I became interested in grammar complexity of regular language. Prior to searching for literature, I tried to investigate it on my own, proving two lemmas from comment below. I am aware of an ...
DG_'s user avatar
  • 411
13 votes
0 answers
218 views

Regular languages accepted by an automaton with at most one transition per letter

I'm interested in the (very restricted) subset of regular languages for which there is an automaton having the following property: for every letter $a$ of the alphabet, the automaton has at most one ...
a3nm's user avatar
  • 9,527
2 votes
1 answer
175 views

What graphs on $\mathbb{N}$ can be encoded as regular languages?

Suppose I represent the natural number 0 by "x", and use the symbol "s" for successor so that I get the following encoding of $\alpha : \mathbb{N} \rightarrow V$ of natural numbers ...
wanderingmathematician's user avatar
1 vote
0 answers
30 views

Decidability of regular partition construction given its existence

Let $G = (N,T,P,S)$ be a context-free grammar where $T,N$ are sets of terminals and nonterminals respectively, $P$ contains all the productions of the grammar, and $S \in N$. If we know that $G$ is LL(...
user35443's user avatar
  • 111
1 vote
0 answers
125 views

Bounds on the construction of regular expressions' intersection operator

There are references on the exponential worst-case of the intersection operator for regular expressions (see [1]). However, I was wondering if there are similar results for the construction process ...
user avatar
13 votes
1 answer
420 views

Planarity of planar finite automata intersection

It was shown that any regular language can be specified by planar $\varepsilon$-free nondeterministic finite automaton (Bezáková, Ivona, and Martin Pál. "Planar finite automata."). Is it ...
gsv's user avatar
  • 421
3 votes
1 answer
140 views

Rewrite relations - proof of correctness

Let $T \subseteq \Sigma^* \times \Sigma^*$ be a regular relation. We define the obligatory rewrite relation over $T$ as follows: $$ R^{obl}(T) := N(T) \cdot (T \cdot N(T))^* $$ $$ N(T) := Id(\Sigma^* ...
Denis Kyashif's user avatar
7 votes
1 answer
392 views

Kleene Algebra for star-free regular expressions

TLDR: Is there a notion of Kleene Algebra for star-free regular expressions? Kleene Algebras are algebraic structures that are equivalent to regular expressions. A Kleene Algebra is an idempotent ...
Faustus's user avatar
  • 193
6 votes
2 answers
2k views

2DFA to 1DFA - Converting two way deterministic finite automata to one way deterministic finite automata

How can I convert a 2DFA to a normal DFA. Is there an algorithm/elegant way to do that ? I've been researching this for a few days but I coundn't find anything. Actually I want to implement that in ...
Karl Millson's user avatar
10 votes
1 answer
762 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 ...
Caleb Stanford's user avatar
6 votes
1 answer
236 views

Complexity of DFA intersection in this specific case?

In general, the size of the DFA that recognizes the intersection of $n$ languages is exponential in $n$. However, in my case I am computing the intersection of a very restricted subset of possible ...
Display Name's user avatar
7 votes
1 answer
181 views

Arranging letters to make a word in a regular language

Fix a regular language $L$ on the alphabet $\{a, b\}$, and consider the following problem. I am given as input: some number $m \in \mathbb{N}$ of copies of the letter $a$, and some number $n \in \...
a3nm's user avatar
  • 9,527
0 votes
1 answer
145 views

Why are all finite languages regular? [closed]

It is said that "All finite languages are regular". But the Pumping Lemma says that, if a language is regular one can find a 'large-enough' word w such that it can be decomposed into w = xyz such ...
stew.nesc's user avatar
2 votes
1 answer
583 views

Oncina-Garcia RPNI algorithm for learning DFAs

The question refers to this paper: ftp://altea.dlsi.ua.es/people/oncina/articulos/asspr1992.pdf Given a sample of $p$ positive and $n$ negative strings, RPNI constructs a consistent DFA in time $O((p+...
Aryeh's user avatar
  • 10.6k
8 votes
0 answers
103 views

Does ${\bf CFLPAD}={\bf PPAD}$?

What happens if we define ${\bf PPAD}$ such that instead of a polytime Turing-machine/polysize circuit, a (non-)deterministic finite/push-down automaton encodes the problem? I asked a similar ...
domotorp's user avatar
  • 14k
1 vote
0 answers
48 views

Question About Turing Machine Computability [closed]

If p is a Turing machine then L(p) = {x | p(x) = yes}. Let A = {p | p is a Turing machine and L(p) is a finite set}. Is A computable? Justify your answer. So I'm trying to figure out how to solve ...
ken6208's user avatar
  • 11
14 votes
2 answers
745 views

Automata learning without counterexamples

In Angluin's automata learning framework, a student aims to learn a regular language $L\subseteq \Sigma^*$ by asking two types of questions to his teacher: Word queries: given $w\in \Sigma^*$, is $w\...
user49692's user avatar
  • 219
9 votes
0 answers
297 views

Shortest string in the intersection of regular languages

Inspired by https://codegolf.stackexchange.com/questions/53310/shortest-universal-maze-exit-string Each of the 138,172 valid mazes can be represented as a DFA with 9 states (including starting and ...
ghosts_in_the_code's user avatar
0 votes
1 answer
854 views

What is the practical importance of making or using a Turing complete language? [closed]

I get what a Turing machine is and what language is a Turing-complete language but when someone introduces me to a new programming language (like Solidity) and says it is Turing complete, what am I ...
n0unc3's user avatar
  • 19