The dfa tag has no wiki summary.
13
votes
2answers
424 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 ...
5
votes
0answers
143 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 ...
-1
votes
0answers
75 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.
11
votes
1answer
198 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 ...
6
votes
1answer
299 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, ...
114
votes
10answers
35k 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
votes
3answers
308 views
Complexity lower bound for regular languages
Suppose I have a regular language $L$, and I would like to lower-bound the complexity of deciding membership in $L$. Suppose I know that the minimal DFA for $L$ has $N$ states.
I would like to claim ...
10
votes
1answer
472 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 ...
13
votes
1answer
384 views
Efficient concatenation of DFAs?
There is theoretical evidence that the naive cartesian-product construction for the intersection of DFAs is "the best we can do". What about the concatenation of two DFAs? The trivial construction ...
5
votes
4answers
254 views
Is it possible to represent a regular expression with bounded captures using a DFA and O(1) additional processing?
It's well known that a regular expression can be converted to a non-deterministic finite state automaton, which can in turn be converted in to a deterministic finite state automaton. These DFAs can ...
9
votes
2answers
204 views
Are non-deterministic tree-walking automata stronger than deterministic ones?
Update: It seems this problem has been studied and solved recently, see this wiki article: http://en.wikipedia.org/wiki/Tree_walking_automaton
And also this survey:
...
2
votes
1answer
269 views
upper bound on the size of a DFA for A|B given the DFAs for A and B?
Given RegEx A and B where the size of the compiled DFAs are m and ...
21
votes
4answers
1k views
DFA intersection in subquadratic space?
The intersection of two (minimal) DFAs with n states can be computed using O(n2) time and space. This is optimal in general, since the resulting (minimal) DFA may have n2 states. However, if the ...
13
votes
3answers
1k 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 ...
