Questions tagged [automata-theory]
Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques
412
questions
1
vote
0
answers
48
views
Equivalence between GNFA and NFA/DFA
In Section 1.3 of the 3rd edition of Michael Sipser’s Introduction to the Theory of Computation, it is proven that regular expressions are equivalent to deterministic finite automatas (DFAs). That is, ...
- 111
7
votes
1
answer
145
views
Complexity of the inevitability problem over monoids
I am interested in the complexity of following problem:
Inevitability problem in monoids
Input: two regular languages $K$, $L$ specified by finite monoids $M_K$ and $M_L$ (+ morphisms and accepting ...
- 143
7
votes
1
answer
317
views
Converting 2-ambiguous NFA to unambiguous NFA
This must be known, but somehow I can't locate a reference about this. Let $A$ be a nondeterministic finite automaton (NFA) over words of an alphabet $\Sigma$. I say that $A$ is unambigous if, for ...
- 8,836
1
vote
0
answers
63
views
Utility of automated alphabet abstraction in automata learning?
In (active) automata learning, a learner tries to infer an appropriate model for a black-box executable state machine by systematically feeding different inputs into it and observing the corresponding ...
1
vote
0
answers
97
views
Real life application of two-way DFA
I am currently studying two-way DFA and I couldn't find and research anything on its real-life applications if there are any. I am very unsure where it could be used and any ideas would be great. tyia
- 11
0
votes
0
answers
62
views
Construction of a PDA for the binary and decimal representation of a number
I have the solution with me for this question but I have really hard time understanding the construction. Can anyone may be break it down in a simpler way?
Problem:
Given $n \in \mathbb{N}^+$. ...
- 11
2
votes
1
answer
136
views
Is $a^m b^n$ where $m - n \sqrt{2} \ge 0$ context-free?
Is the language $a^m b^n$ where $m - n \sqrt{2} \ge 0$ a context-free language? I’m suspecting that it’s not, but I haven’t been able to prove so using the pumping lemma for context-free languages.
...
- 123
4
votes
0
answers
83
views
Linear-time maze exploration for finite automaton with pebbles?
Blum and Kozen have shown that a robot with the computational capabilities of a finite automaton can visit all $n$ cells in a quadratic maze when the robot is equipped with two pebbles which it may ...
- 41
6
votes
0
answers
109
views
What is the Simplest type of automaton that can simulate all DFAs?
During recent research in a somewhat unrelated field (Spin Physics), I stumbled across a subclass of regular languages. The context of the research poses the question what the minimal power of the ...
- 161
5
votes
1
answer
111
views
Logical Equivalents of Finite State Transducers
There's a notion of "regular" function on words in automata theory that corresponds nicely to functions in WS1S/Büchi Arithmetic/the logic of words with a prefix and equal-length relation. ...
- 279
3
votes
0
answers
74
views
State-based vs. transition-based definitions of alternating automata
Maybe this is a naïve question but I'm having difficulties finding the answer in the literature.
Alternating finite automata (AFA) are usually defined in modern literature in the following terms. An ...
- 1,558
0
votes
0
answers
62
views
Number of quantifier alternations in prenex form of a formula
I'm currently studying hyperlogics and in particular HyperLTL/CTL*.
In model checking algorithms for such logics the number of quantifier alternations appearing in a formula can play an important role ...
0
votes
0
answers
99
views
The difference between the 1st and 2nd editions. "Compilers Principles, Techniques, and Tools" by Aho, Sethi and Ullman
I bought "Compilers Principles, Techniques, and Tools 1st Edition" by Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman long years ago and it has been sitting on my bookshelf ever since.
I ...
- 101
4
votes
1
answer
173
views
Pumping lemma for CFL intersection
The class of context-free languages is not closed under intersection. For example, the language $L=\{a^nb^nc^n : n\geq 0\}$ is not context-free, but it is an intersection of two context-free languages....
- 303
11
votes
12
answers
5k
views
Theoretical Computer Science vs other Sciences?
So I‘m in my fifth semester studying Computer Science at a German university, so I‘ve only scratched the surface of Theoretical Computer Science, namely Logic, Formal Languages, Automata Theory, ...
- 127
4
votes
0
answers
68
views
Equivalent Characterizations of Semilinear Sets
Coming from an automata theory background, the semilinear sets seem like an ideal candidate for having lots of equivalent characterizations.
I am already familiar with a few well known ones:
Sets ...
- 279
6
votes
1
answer
270
views
Relationship between the transition monoid of an automaton and its adjacency matrix
Let $A=(Q,\Sigma, \Delta, q_0, F)$ be an NFA over an alphabet $\Sigma$, $M(A)$ be its transition monoid.
For all $a\in\Sigma$, let $S_a\in\mathbb{B}^{|Q|\times|Q|}$ be the adjacency matrix of $A$ ...
- 1,558
5
votes
0
answers
144
views
Arithmetization of finite automata
Is there any standard way to encode the language accepted by a finite automaton by an arithmetic formula?
A particular way of doing this would be to extend the language of existential integer linear ...
- 919
2
votes
1
answer
415
views
Are regular expressions inherently more difficult to construct than DFAs for humans?
When I am asked to construct a regular expression and DFA that would accept a language $L$, I usually find it much easier to construct the DFA (almost coming mechanically for me) than it is to ...
- 1,058
3
votes
2
answers
109
views
Encoding of finite automata in Intersection Non-Emptiness problem
The intersection non-emptiness problem is defined as follows:
Given a list of deterministic finite automata as input, the goal is to determine whether or not their associated regular languages have a ...
- 919
1
vote
0
answers
86
views
Alternative notions of bisimulation
Suppose $(S, \Lambda, \rightarrow)$ is a labeled transition system. A bisimulation is a relation $R \subseteq S \times S$ s.t. $\forall \alpha \in \Lambda$ and $\forall p, q \in S$ with $R(p,q)$,
$\...
- 11
3
votes
3
answers
397
views
Intersection non-emptiness problem over regular expressions and NFA
The intersection non-emptiness problem is defined as follows:
Given a list of deterministic finite automata as input, the goal is to determine whether or not their associated regular languages have a ...
- 919
3
votes
1
answer
171
views
Algorithms for equivalence of 2 way finite automata (2DFA)
I'm interested in the computational complexity of deciding equivalence of 2DFAs.
It is known that converting 2DFA to DFA can incur a blow up in states. However I'm not sure whether this automatically ...
- 135
1
vote
0
answers
137
views
Definition in some old paper about formal power series (automata theory) Part 2
I now know that $K \langle A \rangle$ is the set of all formal power series with finite support for some alphabet $A$ and field $K$. Now I have another question.
Later this expression comes up $\...
- 11
0
votes
0
answers
72
views
Definition in some old paper about formal power series (automata theory)
I have a question about a term in a paper about formal power series. It was never defined but the author used $K \langle A \rangle$, what set is $K \langle A \rangle$? Here $K$ is a field (commutative ...
- 1
2
votes
0
answers
46
views
Applying Angluin's automata learning to build Tree Automata
I have two different questions: a broad question (Q1) and a specific question (Q2).
Q1: Is there any established or well-accepted mechanism to learn tree automata based on Angluin's style of learning ...
- 21
11
votes
1
answer
165
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,124
1
vote
1
answer
55
views
What is region construction in timed automata?
I've recently started self-learning timed automata.
There's this theorem in there that a timed automaton can be converted to a DFA using a "region" construction. I've looked up references on ...
- 123
4
votes
1
answer
89
views
Is there any context-free language that is inherently ambiguous as an indexed language
Indexed languages are defined as being produced by indexed grammar.
Is there any context-free language that is inherently ambiguous as an indexed language? That is, is there a context-free language ...
- 101
5
votes
1
answer
99
views
Is there any inherently ambiguous indexed language?
Indexed languages are defined as being produced by an indexed grammar.
My question is: Is there an indexed language such that there is no indexed grammar that can produce every word of the language in ...
- 101
3
votes
1
answer
202
views
Most non-deterministic automaton
My question is about how to construct, given a number n, an NFA with n states which gets converted to a complete (i.e., with no omitted transitions) DFA with exactly $2^n$ reachable states (even ...
- 141
11
votes
1
answer
286
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,124
4
votes
1
answer
132
views
Characterization of lengths of words accepted by DFAs
Let $M$ be an arbitrary DFA. For each $n \in \mathbb{N}$, let $f_M(n)$ be the number of words of length $n$ accepted by $M$. Then, consider the set of all such $f_M$ for all DFAs $M$.
Is there a nice ...
- 1,124
-1
votes
1
answer
89
views
What set of sequential 2-bit inputs would it take for any system with 2 bits of memory to not be able to know it is not being tested?
In a computer game, a player is tasked with making a sequential circuit that takes two one-bit inputs (for a total of four combinations) and outputs a bit depending on both the current input and the ...
- 99
2
votes
0
answers
79
views
Nondeterministic polynomial time languages with linearly bounded certificates
Define the class $X$ of languages by the condition that a language $L$ over alphabet $\Sigma$ is in $X$ iff there are a constant $c > 0$ and a polynomial-time checking relation $R$ such that for ...
- 191
0
votes
1
answer
147
views
Where to read about PSO (partial store order) memory model
I have been reading about TSO (total store order) memory models for concurrent programs, but I can not find resources for PSO (partial store order) memory models. Can someone please point to resources....
1
vote
1
answer
135
views
Bounded non-emptiness intersection of deterministic context-free grammars
Let A and B be two determinstic context-free grammar, and let N be an integer: What's the complexity of deciding if the intersection of the languages accepted by A and B over all strings of length ...
- 11
5
votes
1
answer
170
views
Alternative to LBA for recognising context-sensitive languages
I've always felt that there's no "canonical" automata for recognising context-sensitive languages. Much like there's DFA for regular, PDA for context-free and Turing machines for RE.
I'm ...
9
votes
0
answers
105
views
Expressiveness of pushdown automata whose stack height sequence is unambiguous
I consider pushdown automata on an alphabet $\Sigma$, which are intuitively finite automata with a stack. Formally, a pushdown automaton $A = (Q, q_0, F, \Gamma, \Delta)$ is a finite set $Q$ of states,...
- 8,836
13
votes
1
answer
445
views
Complexity of NFA to DFA minimization with binary threshold
What is the complexity of the following problem?
Given an NFA $A$ and a number $k\in \mathbb{N}$ in binary encoding, does there exist a DFA $B$ with at most $k$ states such that $L(A)=L(B)$?
...
- 5,521
5
votes
1
answer
173
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, ...
- 541
3
votes
1
answer
597
views
Determinising unambiguous automata without exponential blowup
Is it possible to determinise unambiguous finite automata without exponential blowup in the number of states? I think it should not be possible but I am unable to come up with counterexamples.
- 131
0
votes
1
answer
120
views
Complexity for universal Counter Machine with {0,1}-valued registers
Consider a universal $\{0,1\}$-$k$-counter machine where each of the $k$ registers has a value in $\{0,1\}$ (as opposed to any non-negative integer in the usual formulation), and there are states $q_1,...
- 1
2
votes
1
answer
151
views
Does a finite, polynomially-bounded CFG translate into a polynomially-bounded DFA?
We are given a family of context-free grammars $\{ G_1, G_2, G_3, ..., G_n, ...\}$ where each $G_n$ generates strings only of length $n$ and obeys other constraints specified below. We want to study ...
- 414
3
votes
2
answers
176
views
Translation of Counter-free automata into Linear Temporal Logic
There is a well-known equivalence between counter-free automata and Linear Temporal Logic (which is cited for example by [1]). However, I cannot find a concrete way to obtain an LTL formula from a ...
- 1,558
16
votes
0
answers
417
views
Is this problem on unambiguous finite automata NP-complete?
An unambiguous finite automaton (UFA) is a nondeterministic finite automaton (NFA) such
that each word has at most one accepting path. In this post, for $n\in \mathbb{N}$, what I call an $n$-UFA (resp....
- 1,227
6
votes
1
answer
183
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
3
votes
1
answer
102
views
Conditioning Probability on a Language With Measure 0
Let $\Sigma = \{ 1, 2, \ldots, n\}$ be some alphabet. Assume that you have a coin with n-sides (each side corresponds to a letter in $\Sigma$), and we get each letter with equal probability. Now you ...
- 257
2
votes
0
answers
99
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
4
votes
1
answer
675
views
Can we efficiently convert from NFA to smallest equivalent DFA?
Definitions
For any automaton $X$, let $L(X)$ denote the language recognized by $X$.
For any language $L$, let $sc(L)$ denote the number of states in the smallest DFA $X$ such that $L = L(X)$.
...
- 5,065