Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

Questions tagged [dfa]

Questions about deterministic finite automata

Filter by
Sorted by
Tagged with
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'...
Canadian goose's user avatar
261 votes
11 answers
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 ...
PhD's user avatar
  • 5,325
20 votes
1 answer
3k views

What is the number of languages accepted by a DFA of size $n$?

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,...
Janoma's user avatar
  • 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 ...
Michael Wehar's user avatar
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 ...
vzn's user avatar
  • 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 ...
a3nm's user avatar
  • 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 ...
Wesner Moise's user avatar
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, ...
BlueBomber's user avatar
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 ...
Jendas's user avatar
  • 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 ...
Lev Reyzin's user avatar
  • 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 ...
Zach Hunter's user avatar
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 $...
vzn's user avatar
  • 11k
3 votes
1 answer
236 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 ...
vzn's user avatar
  • 11k