Questions tagged [automata-theory]
Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques
2
votes
1answer
83 views
Applications of Christol theorem
I'm looking forward to know about applications of Christol theorem mentioned in Jefrrey Shallit's Number theory and formal languages. One of them is purely algebraic: if $f, g \in \mathbb{F}_q[[z]]$ ...
9
votes
0answers
71 views
Are there cascade decompositions of machines that are more general than finite automata?
The idea of decomposing automata and their associated semi-groups into irreducible sub-components is due to Krohn & Rhodes and has been explored relatively thoroughly. Krohn & Rhodes gave an ...
7
votes
2answers
298 views
Are all turing machines paths predictable?
I was recently studying partial solutions to the halting problem and came across the problem which I discuss below. In particular I was studying when it was computable to tell if a turing machine has ...
-1
votes
0answers
39 views
What is the difference between derivation tree and total tree?
What is the difference between derivation tree and total tree?explain in example?How derivation tree and total tree read the words.
1
vote
0answers
34 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 ...
12
votes
1answer
576 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\...
4
votes
0answers
62 views
Libraries for programming automata and Turing machines
What are the most useful libraries around for coding related to automata and Turing machines?
By useful I mean the number of functions and algorithms supported by it.
9
votes
0answers
99 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 ...
2
votes
1answer
71 views
Can a det. $k$-counter machine ($k \geq 2$) be simulated by a det. $k'$-counter machine using non-$\epsilon$-moves followed by $\epsilon$-moves?
I have a question concerning deterministic $k$-counter machines, for $k \geq 2$. Recall that in this context, the determinism is expressed by the fact that the machine can never face a choice between ...
2
votes
0answers
68 views
Characterization of deterministic pushdown automata
Is there any known characterization for deterministic pushdown automata (DPDA)?
For example, visibly pushdown automata(VPA) is a subclass of DPDA, which is characterized by following syntactic ...
1
vote
0answers
52 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
1answer
87 views
“Combining” two mealy machines [closed]
How could you combine two mealy machines, the first one $M_1$ has as input $\sum_{1}^*$ and as output $\sum_{2}^*$,
the second machine $M_2$ uses the output $\sum_{2}^*$ as the input and outputs $\...
3
votes
3answers
100 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
118 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
39 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.
5
votes
1answer
96 views
Closure of Recognizable Languages under Kleene Star: Algebraic Proof?
Let $Rec(\Sigma)$ be the class of languages over $\Sigma^*$ recognizable by finite monoids.
To show that $Rec(\Sigma)$ is closed under Kleene star, one would usually refer to the equivalence of ...
2
votes
1answer
227 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 ...
6
votes
1answer
158 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 ...
-1
votes
1answer
40 views
Push Down Automata [closed]
Can we put more than one element in stack at a time.
Actually I am asking that this transition function is valid for PDA:
∆(q,a,z)=(q',aaz)
Where:
q and q' are states
a is input symbol
z is starting ...
3
votes
0answers
83 views
Looking for a specific tree automata model
is there any tree automata model over unranked trees (that is with unbounded number of children for each node), such that:
Checking non-emptiness and universality is decidable in elementary time,
...
22
votes
2answers
465 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 ...
4
votes
1answer
205 views
Is it known if $CFL \subseteq NSPACE(o(log^2(n)))$?
$CFL$ is the class of context-free languages.
Question
Is $CFL$ known to be solvable in $o(log^{2}(n))$ non-deterministic space? What about $DCFL$?
-1
votes
1answer
86 views
When designing a DFA, am I allowed to design two separate Machines and perform an Intersection on them? [closed]
I am trying to design a DFA s.t. The set of strings in x ∈ {0, 1}∗
such that the number of zeros is a multiple of 3 and the number of one's is even.
My idea was to create two Machines M1 = (Q1, Σ, δ1,...
14
votes
1answer
693 views
Complexity of the problem of words with fewest distinct letters accepted by a finite automaton
Given a finite (deterministic or nondeterministic, I don't think this has much importance) automaton A and a threshold n, does A accept a word containing at most n distinct letters?
(By k different ...
13
votes
1answer
133 views
Regular language that discriminates between two deterministic CFGs
Suppose you are given two deterministic push down automata which recognize languages $A$ and $B$, and wish to determine whether there is a regular language $R$ such that $A \subseteq R$ and $R \cap B =...
7
votes
1answer
124 views
Random Deterministic Automata
I am familiar with the term of random graphs, such as $G(n,p)$- a distribution over simple undirected graphs with $n$ vertices, where each edge appears in a graph w.p. $p$. That is, each graph $G=(V,E)...
1
vote
1answer
100 views
Set of languages that can represent every c. e. languange
Could we find any set of languages $S$, such that it can represent every c. e. languange as it's union, intersection, complement, production(times of element ), and $S\subset X$, where $X\subseteq c.e....
3
votes
1answer
61 views
Can any c.e. language with infinite words be decomposed into infinite CFLs with infinite words?
Suppose $L$ is a computably enumerable language, can it be decompose into infinite CFLs with infinite words ?
$$L=\bigcup_{L_i\in CFL }^{\infty}L_i$$
Second question: if it is possible that every $L$...
-1
votes
1answer
71 views
Is there an inherently ambiguous language which can not be recognized by Deterministic LBA?
Is there inherently ambiguous language which can not be recognized by Deterministic LBA?
For example, $L=\{wv: w,v=(x|y)^*, w=w^R,v=v^R\}$, is there any deterministc LBA that recognizes $L$ ?
1
vote
0answers
455 views
Equality Constraints over Sets with Tree Automata
Tree Automata can be used to model sets of values of a Herbrand Universe, for example, to model possible values in a functional program.
Systems of subtype constraints over set expressions have ...
5
votes
1answer
163 views
What is the motivation behind defining Deterministic Looping Automata?
I was wondering about what could possibly be the motivation behind defining the deterministic looping automata? What puzzles me is that they accept a word iff they have a run on it!
I believe they ...
2
votes
1answer
209 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 $\...
5
votes
1answer
1k views
Is Hartmanis-Stearns conjecture settled by this article?
The paper
"On the computational complexity of algebraic numbers: the Hartmanis--Stearns problem revisited"
by Boris Adamczewski, Julien Cassaigne, Marion Le Gonidec
https://arxiv.org/abs/1601....
0
votes
0answers
101 views
What are ordered automata?
recently my supervisor told me of ordered automata, however, I searched for material on the internet about them and did not find, could someone explain me what they are or recommend link with material ...
9
votes
3answers
257 views
Class of languages recognizable by single-tape 3-state TMs
I have for a while been curious about Turing Machines with exactly one tape and exactly 3 states (namely the start state $q_0$, the accept state $q_{accept}$, and the reject state $q_{reject}$). Note ...
1
vote
0answers
61 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 ...
1
vote
0answers
97 views
Convenient forms of Turing machines
Let us suppose that I have defined a new convenient form of the Turing machine for processing of some specific sort of commonly used structures.
This form of TM contains some specific features ...
6
votes
1answer
409 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 ...
7
votes
1answer
217 views
Has there been a study of circuits operating on arrays?
Much ink has been spilled studying the theory surrounding computation by combinatorial circuits operating on bits or boolean values - with AND, OR and NOT gates (as those are enough to implement any ...
10
votes
1answer
186 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 ...
3
votes
1answer
79 views
Giving a finite collection of infinite words “complex” enough with respect to automata measure
We consider acceptance by Büchi automata. Let $X = \{0,1\}$ and $X^{\mathbb N}$ the set of all infinite sequences. Then for each $n$ do we have a finite collection $\{ \xi_1, \xi_2, \ldots, \xi_k \}$ ...
1
vote
2answers
51 views
Algorithms to synthesize optimal plans satisfying temporal logic constraints
I know how NuSMV can be applied on a model to check if certain temporal logic statements are satisfied, particularly LTL. I also know of the LTL to BA conversion routines available online.
I am ...
9
votes
1answer
461 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$ :
...
7
votes
1answer
155 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 $...
10
votes
1answer
190 views
Automata recognizing $X^*$ for a finite code $X$
Let $\Sigma$ be a finite alphabet. A code $X$ over $\Sigma$ is a subset of $\Sigma^*$ such that each word in $X^*$ can be uniquely represented as a concatenation of words in $X$. A code $X$ is finite ...
17
votes
1answer
899 views
Quadratic relationship between nondeterministic and deterministic space?
Savitch's theorem shows that $\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)$ for all large enough functions $f$, and proving that this is tight has been an open problem for decades.
Suppose ...
6
votes
2answers
364 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
2answers
255 views
Number of minimal DFAs of size at most $m$?
Let $\Sigma$ be an alphabet of size $2$, and consider minimal DFAs whose size is bounded by at most $m$. Let $f(m)$ denote the number of different such minimal DFAs.
Can we find a closed-form ...
2
votes
1answer
76 views
CFGs in a certain normal form
Consider Context-Free Grammars with rules of the form $S\to\epsilon$
or $A\to aB | Ba|a$,
meaning that any nonterminal other than $S$ can be replaced by a terminal, or by a pair of letters exactly one ...
7
votes
1answer
349 views
Shortest string in the intersection of a context-free language and a regular language
For a language $X$, define $ss(X) = \min_{x\in X} |x|$, the length of the shortest string in $X$. For simplicity, we define $ss(\emptyset)=0$.
Let $L$ be a context-free language generated by a context-...
