Skip to main content

Questions tagged [dfa]

Questions about deterministic finite automata

9 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9 votes
0 answers

Shortest string in the intersection of regular languages

Inspired by Each of the 138,172 valid mazes can be represented as a DFA with 9 states (including starting and ...
ghosts_in_the_code's user avatar
6 votes
0 answers

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, ...
gsv's user avatar
  • 421
6 votes
0 answers

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 ...
Thomas Tappeiner's user avatar
6 votes
0 answers

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 ...
domotorp's user avatar
  • 14.1k
5 votes
0 answers

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 ...
D.W.'s user avatar
  • 12.1k
2 votes
0 answers

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-...
Dan's user avatar
  • 121
2 votes
0 answers

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. ...
Wickoo's user avatar
  • 386
1 vote
0 answers

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 ) ...
Coping Forever's user avatar
1 vote
0 answers

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
user69786's user avatar