# Questions tagged [dfa]

13 questions
Filter by
Sorted by
Tagged with
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'...
100k views

### What is the enlightenment I'm supposed to attain after studying finite automata?

I've been revising Theory of Computation for fun and this question has been nagging me for a while (funny never thought of it when I learnt Automata Theory in my undergrad). So "why" exactly do we ...
• 5,325
3k views

The question is simple and direct: For a fixed $n$, how many (different) languages are accepted by a DFA of size $n$ (i.e. $n$ states)? I will formally state this: Define a DFA as $(Q,\Sigma,\delta,... • 1,406 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 4 votes 3 answers 718 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 23 votes 1 answer 986 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 ... • 9,409 17 votes 3 answers 2k views ### Can a nondeterministic finite automata (NDFA) be efficiently converted to a deterministic finite automata (DFA) in subexponential space/time? Twenty years ago, I built an regular expression package that included conversions from regular expressions to a finite state machine (DFA) and supported a host of closed regular expression operations ... • 311 14 votes 1 answer 5k views ### What algorithms exist for construction a DFA that recognizes the language described by a given regex? All of my textbooks use the same algorithm for producing a DFA given a regex: First, make an NFA that recognizes the language of the regex, then, using the subset (aka "powerset") construction, ... • 251 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 12 votes 1 answer 891 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 ... • 12k 11 votes 2 answers 424 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 ... • 625 10 votes 1 answer 265 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
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 ...