# Questions tagged [dfa]

Questions about deterministic finite automata

63 questions
Filter by
Sorted by
Tagged with
1 vote
0 answers
41 views

### Constructing a DFA with $n$ states for which $L*$ needs $n$ equivalence queries

I'm working on constructing deterministic finite automata (DFAs) with a specific learning complexity when using the L* algorithm developed by Dana Angluin. My goal is to create a DFA of size ( n ) ...
2 votes
1 answer
110 views

### What is the current state of the art on exact identification of DFAs with a maximum N states

This is a question about the blackbox grammar inference of deterministic finite state automata (DFAs). In particular I want to ask about when one can exactly identify the target DFA using queries to ...
8 votes
3 answers
322 views

### Relationship between size of Boolean functions and DFAs

Are there any works that study the relationship between Boolean functions and the size of the minimal DFAs required to represent those Boolean functions? Boolean functions refer to the usual ...
• 181
7 votes
1 answer
217 views

• 9,269
6 votes
2 answers
2k 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 ...
6 votes
1 answer
233 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 ...
• 347
8 votes
1 answer
223 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 ...
2 votes
1 answer
563 views

• 427
10 votes
2 answers
482 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
215 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
985 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
278 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

• 11k
4 votes
3 answers
698 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
4k 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
161 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 ...
• 14k
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,439