Questions tagged [automata-theory]
Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques
335
questions
-2
votes
0answers
10 views
What does “proven constructions” mean in the context of Finite Automata? [on hold]
I was working out some beginner problems in Automata theory, and have encountered this question:
"Using proven constructions automatically generate a DFA which only accepts round trips of even cost"...
1
vote
1answer
59 views
Are endmarkers necessary for Deterministic Pushdown Automata?
I asked this question here: https://cs.stackexchange.com/questions/116758/are-endmarkers-necessary-for-deterministic-pushdown-automata
In the book by Kozen (Automata and Computability), the ...
-1
votes
0answers
34 views
Prove the Stack-Turing Machine is equivalent to the Classic TM
Consider a “Stack-Turing Machine” variant that operates with one infinite tape and one stack. At each step through the tape, the machine reads the input from the current tape location and from the top ...
0
votes
0answers
56 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 ...
9
votes
1answer
151 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
39 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
49 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
116 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
92 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
58 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
71 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
89 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
...
1
vote
0answers
58 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
73 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
161 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
154 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
96 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
50 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,...
8
votes
1answer
222 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
149 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
153 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, ...
4
votes
1answer
165 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
121 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
389 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
263 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
114 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
98 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
390 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
639 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
73 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
143 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
89 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
77 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
160 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
109 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
57 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
112 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
233 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
192 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
43 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
90 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
494 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
282 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 ...
12
votes
1answer
138 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
134 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)...
