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
-2
votes
0answers
33 views

regular expression over subset of language [closed]

im learning theoretical computer science regular expressions i need to find regular expressions for language in $\sum {1,2,3 }$ a.) language with at most one 1 and at most one 2 $0^{*}10^{*}20^{*}...
4
votes
0answers
97 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 \...
0
votes
1answer
69 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
1answer
98 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+...
8
votes
0answers
96 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 ...
1
vote
0answers
40 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 ...
13
votes
2answers
637 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\...
9
votes
0answers
124 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 ...
-1
votes
1answer
136 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 ...
1
vote
0answers
57 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\}$ ...
3
votes
3answers
107 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 ...
9
votes
1answer
133 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 $...
-4
votes
1answer
53 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.
2
votes
1answer
230 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 ...
7
votes
1answer
185 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 ...
22
votes
2answers
486 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 ...
11
votes
1answer
271 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 ...
-3
votes
1answer
61 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?
1
vote
0answers
93 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 ...
2
votes
1answer
214 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 $\...
1
vote
0answers
78 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 ...
6
votes
1answer
423 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 ...
12
votes
0answers
285 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 $...
9
votes
1answer
232 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 ...
8
votes
1answer
510 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$ : ...
6
votes
1answer
168 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 $...
9
votes
1answer
263 views

Complexity of checking if two words have an interleaving in a language

For a fixed language $L$ on some alphabet $A$, let us consider the following problem, that I call $L$-INTERLEAVING: Input: two words $u, v \in A^*$ Output: whether there exists an interleaving of $u$ ...
6
votes
2answers
459 views

In the context of regular languages, must the alphabet be finite?

In The Theory of Parsing, Translation, and Compiling, Volume I, Section 0.2.1 (p.15 / 1972), Aho and Ullman casually write that "[a]n alphabet need not be finite or even countable, but for all ...
9
votes
1answer
183 views

Regular languages and constant communication complexity

Let $L \subseteq A^*$ be a language, and define $f_L\colon A^* \times A^* \to \{0, 1\}$ by $f_L(x, y) = 1$ iff $x\cdot y \in L$. I'm searching for a reference for: Proposition. $L$ is regular iff ...
1
vote
0answers
89 views

Is there a signature of a first-order language that characterize the class of regular languages?

A previous question on this site was about extending the first-order logic with logical constants (quantifiers, fixed-point operators, etc.) to obtain a logical characterization of the class of ...
14
votes
4answers
486 views

Hierarchies in regular languages

Is there any known "nice" hierarchy $L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots$ (may be finite) inside the class of regular languages $L$? By nice here, the classes in each hierarchy capture ...
3
votes
1answer
74 views

Size bound on Büchi automaton for complement

For a given Büchi automaton $\mathcal A = (A, Q, \delta, q_0, F)$ we define a congruence on $A^{\ast}$ by $$ \begin{array}{llll} u \sim_{\mathcal A} v & :\Leftrightarrow & \mbox{for all }s,s' ...
1
vote
0answers
99 views

Why is an automaton on finite words co-deterministic iff its transitions are co-deterministic

In the article Automata and semigroups recognizing infinite words an automaton is specified by $\mathcal A = (Q, A, E, I, F)$ where $I$ is a set of initial states and $F$ a set of final states, $Q$ ...
3
votes
2answers
155 views

A property of suffix-free regular languages of maximal state complexity for the reverse operation

Let $L$ be a regular suffix-free language whose complete minimal automaton has $n$ states and that the minimal automaton of $L^R$ has exactly $2^{n-2}+1$ states. Let $p, q$ be two distinct states of ...
2
votes
0answers
77 views

Proof of the equivalence of Muller automata and Parity (or Rabin chain) automata

Let $A$ be some finite alphabet and $\mathcal A = (Q, \delta, q_0)$ be some determinisitic finite automaton. Then $\mathcal A$ accepts infinite words $\xi \in A^{\omega}$ according to the Muller ...
13
votes
3answers
1k views

On the realisation of monoids as syntactic monoids of languages

Let $L \subseteq X^{\ast}$ be some language, then we define the syntactic congruence as $$ u \sim v :\Leftrightarrow \forall x, y\in X^{\ast} : xuy \in L \leftrightarrow xvy \in L $$ and the quotient ...
5
votes
1answer
170 views

Useful equivalence relations on $X^{\ast}$ (like the Nerode and syntactic equivalence relations)

I want to have an overview of all the meaningful equivalence relations defined on $X^{\ast}$, in particular when the languages in question are regular. They typically arise in connection with the ...
9
votes
1answer
169 views

Do bounded-visit nondeterministic linear bounded automata recognize only regular languages?

Do bounded-visit nondeterministic linear bounded automata recognize only regular languages? By a nondeterministic linear bounded automaton (nLBA) I mean a single-tape nondeterministic Turing machine ...
14
votes
2answers
558 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{...
6
votes
2answers
241 views

FSM transducer sequential composition decidability

this is a followup/ sequel to this recent question which was answered, this one presumably significantly harder. consider a deterministic FSM transducer $F$ and its mapping $F(x)$ of an input word $x$....
10
votes
1answer
212 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 $...
-2
votes
1answer
210 views

Writing a regular expression for character set $\Sigma = \{a,b,(,)\}$ that not have a parenthesis inside a parenthesis [closed]

Let character set $\Sigma=\{a,b,(,)\}$. I want to write a regular expression for the language $L$ that does not have a parenthesis inside a parenthesis. For example, $(abaab)(bbbaa) \in L$, while $(...
10
votes
0answers
101 views

Chomsky-Schützenberger for Deterministic CFLs

Is there a Chomsky-Schützenberger representation theorem for deterministic CFLs? Knowing precisely the class of morphisms under which DCFL is closed, such a theorem would probably be of the form: $...
3
votes
1answer
108 views

Deterministic Parity Automata require unbounded index

Deterministic parity automata $(Q, \Sigma, q_0, \Delta, c)$ are powerful enough to recognize all $\omega$-regular languages. However, the number of priorities they require for a language can become ...
0
votes
2answers
171 views

Example of R and G when $R \subseteq L(G)$ is undecidable [closed]

Could anybody provide an example of regular language R and context-free grammar G such that $R \subseteq L(G)$ is undecidable. Of course, if such language could be constructed. Thanks.
6
votes
1answer
215 views

Who introduced nondeterministic M-automata, and proved that the finite ones recognize the rational sets over M?

Let $M$ be a monoid. The family $\operatorname{RAT}(M)$ of rational sets over $M$ is defined inductively: If $L$ is a finite subset of $M$, then $L\in\operatorname{RAT}(M)$. If $K,L\in\operatorname{...
2
votes
1answer
2k views

Deciding whether a context-free language is regular [closed]

Does anyone know whether the following decision problem is decidable: Given a context-free language $L$, is $L$ regular? Here $L$ can be expressed, e.g., using a context-free grammar. Does anyone ...
23
votes
1answer
1k 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 ...
3
votes
2answers
244 views

computing maximal bit density over a FSM

let $L$ be a regular language defined by a FSM over binary symbols $\{0,1\}$. consider a function $f(x)$ on words/ strings that computes "bit density", defined as the number of $1$'s in a word ("...
4
votes
1answer
196 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}$. ...