Questions tagged [automata-theory]
Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques
337
questions
-1
votes
0answers
13 views
Ask for explanation about the composition of weighted transducers
I'm now reading the book Foundations of machine learning and the author introduces weighted transducers in order to define sequence kernels(you can refer to P122 of this book).The author then ...
-5
votes
0answers
28 views
Which of these is regular? [closed]
I've been reviewing past paper questions for an automaton course, and came across a question which effectively asks, which of these languages is regular?
$$
\{\ 0^m1^{(m \times n)}0^n\ \colon\ m,n\ge ...
7
votes
2answers
245 views
Maximum shortest word accepted by pushdown automata
Given a fixed alphabet, consider all deterministic pushdown automata with $n$ states that accept a nonempty language. What is the maximum length of the shortest word accepted by a deterministic ...
7
votes
2answers
267 views
Constraints on sliding windows
Let $L\subseteq \Sigma^*$ be a language of finite words and $n>0$ some integer.
I would like to know if anything is known on the time and space complexity with respect to $n$ to check for ...
4
votes
1answer
167 views
Are endmarkers necessary for Deterministic Pushdown Automata?
In the book by Kozen (Automata and Computability), the transition function of deterministic pushdown automata (DPDAs) is supposed, in contrast with non-deterministic pushdown automata (NPDAs), to ...
0
votes
0answers
57 views
Information theory for Mathematical Physics [duplicate]
What are some good introductory texts on information theory for someone who is classically trained in mathematical physics?
Unfortunately my abilities in computer sciences and formal logic are next ...
10
votes
1answer
158 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 ...
4
votes
0answers
42 views
Translation from LTL with Past to LTL
Has it been charaterized the cost of the translation from LTL with Past to LTL?
In [Gab89] this translation is assumed to be non elementary and in "Temporal Logic with Past is Exponentially More ...
1
vote
1answer
50 views
Can we have more than one Deterministic Finite Automata diagrams for a set of strings? [closed]
Much like many math equations can be simplified. I am wondering if Deterministic Finite Automata diagrams can equal each other while some may be more simplified than others. I am following the youtube ...
5
votes
1answer
117 views
Are PDAs without ϵ moves and with bounded stack operation as powerful as PDAs with them?
It is known that PDAs without $\epsilon$ moves are as powerful as PDAs with them.
However, it seems to me that the proof allows several stack operations in one move. What happens if we allow at most ...
4
votes
1answer
93 views
Deterministic Realtime Languages
Book and Greibach (V. Book, Ronald & A. Greibach, Sheila. (1970). Quasi-realtime languages. Theory of Computing Systems. 4. 97-111. 10.1007/BF01705890.) prove that non-deterministic linear time ...
0
votes
0answers
60 views
Language recongized by a “quasi realtime register machine”?
Counter machines are very powerful. Even two counters suffice for making these Turing complete.
But, in simulating a Turing machine the counter machine encodes in its integers a large amount of data. ...
-2
votes
1answer
73 views
DPDA with parameterized states
I'm considering an extension of Sublime Text's syntax definition format. A syntax definition is, in essence, a specification of a deterministic pushdown automaton. I would like to extend the system to ...
-1
votes
1answer
90 views
What is the formal definition of a stacked based finite state machine?
The formal definition of a finite state machine is as follows:
A FSM is a quintuple:
($I$, $S$, $S$0, $T$, $F$)
$I$ - finite, non-empty input set
$S$ - finite, non-empty state set
$S$0 - initial state
...
3
votes
1answer
108 views
Intersection of two deterministic parity automata
Given two deterministic parity automata $A_1=(Q_1,\Sigma,\delta,q_{01},c_1)$ and $A_2=(Q_2,\Sigma,\delta,q_{02},c_2)$ with the finite set of states $Q_i$, the finite alphabet $\Sigma_i$, the ...
3
votes
1answer
76 views
Agnostic query learning for DFAs
Angluin's membership+equivalence query algorithm allows to efficiently and exactly learn a target $n$-state DFA. But what if the target DFA is huge, or the target concept is not even a regular ...
6
votes
1answer
162 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 ...
0
votes
1answer
193 views
Where does a C-like language without heaps belong in the automata hierarchy?
Assume that the language C', unlike C, has well-defined semantics, but has similar features: pointers and manual memory management through malloc and free. Assume that C'' is the same as C' without ...
2
votes
0answers
98 views
Notion of “quotient” or “inverse” for recognizable tree languages?
Related to my previous question but this time I have a better idea of what I'm actually asking.
I'm looking at the following operation on recognizable tree languages (i.e. regular tree grammars, ...
2
votes
0answers
53 views
Regular Tree Languages are closed under quotient?
The Wikipedia page for Regular Tree Grammars notes that if $L_1$ and $L_2$ are regular tree languages, than $L_1 \setminus L_2$ is as well. However, it doesn't define this quotient operation for trees,...
9
votes
1answer
235 views
Turing Machines as Coalgebras
I'm looking to write a survey on the method of representing the dynamics of state-based computation within the framework of coalgebras. So far I've managed to find papers on coalgebra representations ...
8
votes
1answer
151 views
A conjecture related to the Cerny conjecture - counterexample/reference request
The Cerny conjecture is the statement that any synchronizing automaton with $n$ states has a synchronizing word of length at most $(n-1)^2$. The best current upper bound for the length of a ...
3
votes
2answers
158 views
Compactness of domino tilings
I've read in Lemma 2 of the paper 1 that if every square region of the plane admits a tiling, then the whole plain admits a tiling, but the proof is omitted. This sounds like a compactness property, ...
5
votes
1answer
207 views
Name for a special family of languages?
I was wondering whether there is a standard name in the literature for the following family $\mathcal{F}$ of languages over any finite alphabet $\Sigma = \{a_1,\ldots,a_k\}$:
$\mathcal{F}$ consists ...
2
votes
1answer
153 views
Automata as term rewriting systems
It came to my mind that automata (say to start DFA) can be thought as a special kind of rewriting systems. So if one has a word w , one tries to reduce it to the $\epsilon$ word. In other words ...
9
votes
3answers
395 views
Continuous mathematics and formal language theory
Whether there are some results on solving formal languages problems using mathematical analysis, continuous mathematics.
For example, solving the intersection non-emptiness problem for a context-free ...
11
votes
2answers
311 views
Does a given regular language contain an infinite prefix-free subset?
A set of words over a finite alphabet is prefix-free if there are no two distinct words where one is a prefix of the other.
The question is:
What is the complexity of checking whether a regular ...
4
votes
1answer
115 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
102 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
437 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
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
641 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
75 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
147 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
91 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 ...
3
votes
0answers
84 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
59 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
173 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
111 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
137 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
59 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.
6
votes
1answer
124 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
234 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
201 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
45 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
91 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,
...
23
votes
2answers
513 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
293 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
91 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,...
13
votes
1answer
698 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 ...
