Questions tagged [dfa]
Questions about deterministic finite automata
60
questions
6
votes
2
answers
418
views
Error in Robson's proof about separating strings?
One of my students discovered a possible mistake in Robson's classic paper Separating strings with small automata.
The issue is in the proof of Theorem 1, giving the simpler bound $O(\sqrt{n\log n})$.
...
- 13.9k
0
votes
0
answers
38
views
How the correctness of this construction can be proved? [closed]
We are using Myhill-Nerode Theorem algorithm and we want to prove that this algorithm gives us the minimized DFA.
So let $B$ be the minimized DFA obtained by applying the algorithm to the DFA $A$. We ...
6
votes
0
answers
62
views
Updating (minimal) DFA incrementally
Is there algorithm to incrementally update (minimal) DFA? Namely, having relatively large minimized DFA I want to update it incrementally using union and sudtraction with other (relatively small, ...
- 421
1
vote
0
answers
106
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
7
votes
1
answer
227
views
Is DFA language inclusion decidable in quasi-linear time? [duplicate]
Given two DFAs $A_1$ and $A_2$, we want to decide whether $\mathcal{L}(A_1) \subseteq \mathcal{L}(A_2)$. Of course, one can compute whether $\mathcal{L}(A_1) \cap \mathcal{L}(A_2) = \mathcal{L}(A_1)$. ...
- 135
6
votes
0
answers
117
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
-6
votes
2
answers
108
views
I have to make a dfa over the alphabet Σ = { 0, 1, 2 } of strings that end with the same digit twice; e.g., strings that end in 00, 11, 22 [closed]
hi can you please go over my dfa for this and tell me if its correct??
- 1
7
votes
1
answer
205
views
Random Cerny Conjecture
For simplicity, all DFAs will be using the binary alphabet $\{0,1\}$. Let $M$ be a synchronizable DFA. We let $p(M,n)$ be the probability that a random $x\in \{0,1\}^n$ will synchronize $M$.
We define ...
- 603
11
votes
2
answers
406
views
Bounds on this Strategy for Separating Words
Question
Given binary string $z \in \{0,1\}^n$, let $f(z)$ be the smallest integer $k$ such that there exists a DFA with $k$ states, such that reading $z$ from a specific starting state, we end at a ...
- 603
9
votes
2
answers
771
views
Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?
Fix a deterministic finite automaton $A$ defining a regular language on the alphabet $\Sigma = \{0, 1\}$, and call the (Hamming) weight of a word $w \in \Sigma^*$ its number of $1$'s. Given a length $...
- 8,896
6
votes
2
answers
1k
views
2DFA to 1DFA - Converting two way deterministic finite automata to one way deterministic finite automata
How can I convert a 2DFA to a normal DFA. Is there an algorithm/elegant way to do that ?
I've been researching this for a few days but I coundn't find anything. Actually I want to implement that in ...
- 73
6
votes
1
answer
226
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 ...
- 337
8
votes
1
answer
218
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 ...
- 91
2
votes
1
answer
495
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+...
- 10.3k
6
votes
1
answer
190
views
Separating words and graph isomorphism
I wonder if there are any known implications of Babai's recent quasi-polynomial time algorithm for Graph Isomorphism to separating words by DFA's.
In both cases the ultimate goal is to differentiate ...
- 13.9k
9
votes
0
answers
284
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 ...
5
votes
1
answer
290
views
Is Bayes optimal RL of a finite set of DFAs feasible?
Let $Q$ be a finite set of states, $\Sigma$ a finite alphabet, $q_0\in Q$ the start state and $F\subseteq Q$ the set of accepting sets. Let $\{\delta_k:Q\times\Sigma\rightarrow Q\}_{k=1}^n$ be a set ...
- 2,151
-1
votes
1
answer
110
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,...
- 17
3
votes
1
answer
465
views
NFA to 2DFA: what are the upper and lower bounds?
Suppose that one has an NFA (from, say, a regular expression). What is the state complexity of turning it into a 2DFA?
- 516
-1
votes
1
answer
78
views
Non equivalent states shortest word [closed]
My textbook contains a theorem that if you have a DFA and two states that are not-equivalent, then there is a differentiating word that has length smaller than amount of states in that DFA.
How do we ...
- 107
2
votes
0
answers
74
views
Structural property of DFAs/NFAs accepting LTL-definable languages
I consider LTL on finite words. In this context, there are a couple of nice equivalence results for a language L:
L is LTL-...
- 121
8
votes
1
answer
1k
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$ :
...
- 427
7
votes
1
answer
213
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 $...
- 427
10
votes
2
answers
465
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 ...
- 427
6
votes
2
answers
211
views
Finite Automata with succinct representation of chains of states
Consider a kind of automata similar to common DFAs or NFAs where it is possible to represent succinctly linear chains of states. In other words, an automaton like this:
could be represented in this ...
- 1,588
16
votes
2
answers
965
views
Is there a well-defined division operation on finite automata?
Background:
Given two deterministic finite automata A and B, we form the product C by letting the states in C be the cartesian product of states in A and states in B. Then, we choose transitions, ...
- 513
-4
votes
1
answer
5k
views
How to check if a the language represented by a DFA is finite [closed]
I am studying regular languages and D FA. I have implemented D FA in Java. I have to write a function which tells if the language represented by a D FA is finite or not.
I need a method or algorithm ...
3
votes
5
answers
1k
views
How to constrain a finite automaton (NFA and DFA) to a tree?
I have a finite automaton by the standard model Hopcroft & Ullman define:
$$
M = (Q, \Sigma, \delta, q_0, F)
$$
Where $\delta$ is the transition function mapping $Q \times \Sigma \mapsto Q$, such ...
- 134
6
votes
2
answers
276
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$....
- 11k
10
votes
1
answer
262
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 $...
- 11k
1
vote
1
answer
1k
views
What is the relation/difference between axiomatic and denotational semantics one one side, and the data flow analysis(DFA) on the other sied?
I am supposed to write a small paper about DFA in OOP for a CS class in theory. But I am required to connect that (DFA) to axiomatic and denotational semantics!
I read few resources about axiomatic/...
- 113
5
votes
1
answer
148
views
When does automaton stay unchanged after string homomorphism?
Suppose we have a string homomorphism $\varphi: \Sigma \rightarrow \Sigma^*$.
Consider the languages in $\varphi(\Sigma^*)$ whose letters are elements of $\varphi(\Sigma)$, so here I do not want to ...
- 13.9k
25
votes
1
answer
1k
views
Finding the smallest DFA that separates two words without using brute force search?
Given two strings x and y, I want to build a minimum size DFA that accepts x and rejects y. One way to do this is brute force search. You enumerate DFA's starting with the smallest. You try each ...
- 5,127
9
votes
1
answer
1k
views
DFA intersection algorithm for special cases
I'm interested in efficient algorithms for DFA intersection for special cases. Namely, when the DFAs to intersect obey a certain structure and/or operates on limited alphabet. Is there any source ...
user30584
-1
votes
1
answer
2k
views
How to XOR automata? [closed]
Say we have 3 DFAs. We know how to OR, AND, or NOT them. But how does one XOR them? There is not one single mention of this online.
x XOR y XOR z = ((x|y)(~x|y)|z) (~((x|y)(~x|y))|z). This is way too ...
- 11
18
votes
2
answers
499
views
Separating words with random DFAs
One of the interesting open problems about DFAs listed in Are there any open problems left about DFAs? is the size of a DFA required to separate two strings of length $n$. I am curious if there any ...
- 3,243
2
votes
0
answers
333
views
Composition of regular expressions with lookahead into DFAs
Let's say we have a regular expression ("a" | "b"(~!"b"))*, written in Perl or other similar languages that support lookahead, which should match a list of a and b's where b's are not followed by b's.
...
- 376
69
votes
10
answers
9k
views
Are there any open problems left about DFAs?
After studying deterministic finite state automata (DFA) in undergrad, I felt they are extremely well understood. My question is whether there is something we still don't understand about them. I don'...
- 612
23
votes
1
answer
961
views
Languages recognized by polynomial-size DFAs
For a fixed finite alphabet $\Sigma$, a formal language $L$ over $\Sigma$ is regular if there exists a deterministic finite automaton (DFA) over $\Sigma$ which accepts exactly $L$.
I am interested in ...
- 8,896
7
votes
1
answer
260
views
Are there any books containing collections of automata problems?
You can find specialized books consisting entirely or problems from particular math domains (e.g. linear algebra, polynomials, combinatorics), but I've yet to find such a book for automata of any kind....
- 179
2
votes
1
answer
713
views
What are good conferences for algorithms about finite automata?
I am writing a research paper, which describes some properties about finite automata. It also provides a couple of algorithms that can measure some aspects of the properties.
Could you point out some ...
- 145
5
votes
0
answers
202
views
Exploring a DFA, with no feedback
Let $M=(\Sigma,S,s_0,\delta)$ be an (unknown) deterministic finite-state automaton (DFA), with alphabet $\Sigma$, statespace $S$, start state $s_0 \in S$, and transition relation $\delta$. I want to ...
- 11.7k
3
votes
1
answer
234
views
Finding self-similar homomorphisms of a FSM transducer
Consider a special case of homomorphisms of FSM transducers (or "generalized sequential machines" in [1]). Let $F$ be a transducer accepting a language $L$, and let $h(x)$ be a homomorphism function ...
- 11k
4
votes
3
answers
663
views
How to minimize a FSM transducer?
In contrast to FSM minimization which is well studied with various algorithms, theorems and has many practical applications, I'm looking for any nontrivial insight, analysis and references to the ...
- 11k
12
votes
2
answers
3k
views
Algorithm for converting very large NFA to DFA
I have really large Non-deterministic finite automaton and I need to convert it to the DFA.
By large I mean 40 000+ states.
So far I have done some experiments and programmed the default algorithm ...
- 223
6
votes
0
answers
160
views
Are k+1 heads better than k for multiread finite automata?
Consider the deterministic (resp. non-deterministic) one-way finite automaton that is defined in the usual way except that it has k heads and in each step can decide which head to move. (It is allowed ...
- 13.9k
16
votes
2
answers
2k
views
minimizing size of regular expression for finite sets
It is known that minimizing the size of a regular expression is PSPACE-complete even if we have a DFA as the language's specification.
What are the results if the language is finite?
One can ...
- 4,367
10
votes
1
answer
400
views
Multi-language DFA minimisation
I'm interested in a slight generalisation of DFA. As usual we have state-set $Q$, finite alphabet $\Sigma$, a $\Sigma^*$-action defined on $Q$ by $\delta : Q\times\Sigma\rightarrow Q$, and initial ...
- 406
-1
votes
0
answers
119
views
How does "δ:Q×Σ→Q" read in the definition of a DFA (deterministic finite acceptor)? [closed]
How do you say "δ:Q×Σ→Q" in English? Describing what "×" and "→" mean would also help.
- 99
12
votes
1
answer
877
views
The Cost of an Equivalence Query for DFA
Inspired by this question, I am curious about the following:
What is the worst-case complexity of checking whether a given DFA accepts the same
language as a given regular expression?
Is this ...
- 11.9k