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.
127
questions
9
votes
2
answers
207
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 ...
- 8,224
3
votes
1
answer
150
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 ...
- 293
11
votes
1
answer
160
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 ...
- 1,015
4
votes
0
answers
51
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 ...
- 8,223
11
votes
1
answer
284
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 ...
- 1,015
0
votes
0
answers
45
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 ...
6
votes
1
answer
177
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}= \...
- 193
5
votes
1
answer
159
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, ...
- 521
5
votes
2
answers
200
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 ...
- 1,165
6
votes
1
answer
182
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, ...
- 4,761
2
votes
0
answers
92
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 ...
- 193
2
votes
1
answer
227
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$ ...
- 12.6k
2
votes
1
answer
148
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 "...
- 146
-1
votes
1
answer
353
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{...
- 157
5
votes
1
answer
97
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 ...
- 411
12
votes
0
answers
188
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 ...
- 8,224
2
votes
1
answer
160
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 ...
1
vote
0
answers
29
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(...
- 111
1
vote
0
answers
119
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 ...
user59861
13
votes
1
answer
349
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 ...
- 361
3
votes
1
answer
132
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^* ...
7
votes
1
answer
342
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 ...
- 193
6
votes
2
answers
640
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 ...
- 73
10
votes
1
answer
724
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 ...
- 852
6
votes
1
answer
214
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 ...
- 327
7
votes
1
answer
177
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 \...
- 8,224
0
votes
1
answer
130
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 ...
2
votes
1
answer
432
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+...
- 10.2k
8
votes
0
answers
102
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 ...
- 13.8k
1
vote
0
answers
47
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 ...
- 11
14
votes
2
answers
714
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\...
- 219
9
votes
0
answers
269
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 ...
0
votes
1
answer
692
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 ...
- 19
1
vote
0
answers
64
views
Rational power series over $\mathbb N \cup \{\infty\}$, rationality of singular part
Let $\Sigma$ be a finite alphabet, and consider the formel power series over $\Sigma$ considered as non-commuting variables with coefficients in the semiring $\mathcal N := \mathbb N \cup \{\infty\}$ ...
- 1,977
3
votes
3
answers
148
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 ...
- 1,977
9
votes
1
answer
221
views
Generalisation of the statement that a monoid recognizes language iff syntactic monoid divides monoid
Let $A$ be a finite alphabet. For a given language $L \subseteq A^{\ast}$ the syntactic monoid $M(L)$ is a well-known notion in formal language theory. Furthermore, a monoid $M$ recognizes a language $...
- 1,977
-4
votes
1
answer
160
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.
- 1
2
votes
1
answer
237
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 ...
- 21
7
votes
1
answer
241
views
Finding a minimal DFA whose language has a desired intersection with another
Suppose I have regular languages $B \subseteq A$, with corresponding (known) minimal deterministic finite automata $M_A, M_B$.
I would like to find another regular language $C$ such that $B = A \cap ...
- 434
23
votes
2
answers
547
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 ...
- 8,224
11
votes
1
answer
606
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 ...
- 2,113
-3
votes
1
answer
69
views
Is there a non regular and regular language where the non regular is not a subset of the regular and the union is regular? [closed]
Does there exist languages $L1$, $L2$ where $L1$ is non regular, $L2$ is regular $L1\not\subset L2$ and $L1 \cup L2$ is regular?
- 103
2
votes
0
answers
128
views
Possibly small circuit complexity class containing REG?
What is the smallest well-known Boolean-circuit complexity class containing all the regular languages over the binary alphabet {0,1}?
If we believe Theorem 2 in
Koucký, Circuit Complexity of ...
user48424
2
votes
1
answer
228
views
Deformation of finite regular languages [closed]
Let $L \subseteq \{0,1\}^n$ be any finite regular language s.t it has an acyclic DFA.
Let $C$ be some class of acyclic DFAs.
Let $\sigma \in S_n$ be a permutation on $n$ symbols. We can apply $\...
- 31
1
vote
0
answers
164
views
Relation between MDPs and non-deterministic finite automatons
I'm confused as to the relation (computability-wise) between markov decision processes and NFAs. Are finite state MDPs expressible as regular grammars? If so, are markov decision processes thus ...
- 121
6
votes
1
answer
454
views
Pumping Lemma over 2 way Automaton
Pumping Lemma essentially implies that for a NFA $N$ having $N_0$ states over a unary language $L_0$ any string belonging to $L_0$ can be obtained by 'pumping' one of the strings that have a length ...
- 783
12
votes
0
answers
305
views
Reference request: exponential growth rates of subsequence-closed languages are integers
This question is migrated from MathOverflow, where it did not receive any answers a year ago.
For a language $L$ over the finite alphabet $\Sigma$, let $L_n$ denote the set of words in $L$ of length $...
- 319
9
votes
1
answer
395
views
Transition monoid membership for DFAs
Given a complete DFA $A=(Q, \Gamma, \delta, F)$, we can define a collection of functions $f_a$ for each $a\in \Gamma$and with $f_a:Q\rightarrow Q$, $f_a(q)=\delta(q, a)$. We can generalize this notion ...
- 1,345
8
votes
1
answer
954
views
NFA to DFA Powerset Construction : A Partial determinization algorithm with trade-off between running time and size for the resulting automata?
Given a NFA $N$ and its equivalent DFA $D$ resulting from the total determinization of $N$ (using powerset construction, for example), the following properties hold for $N$, $D$ and for any word $w$ :
...
- 427
7
votes
1
answer
209
views
Automata : Language Containment, Minimality & Graph Homomorphism
Given two DFAs $A$ and $B$ defined on the same alphabet, a (graph) homomorphism $h:A \rightarrow B$ from $A$ to $B$ is a mapping of the states of $A$ into the states of $B$ such that :
if the state $...
- 427