A DFA is a deterministic finite automaton, a simple model of computation. It is one way to model regular languages. Each DFA consists of a finite set of states and a transition function between those states describing how the state of the machine changes in response to new input. DFAs are closely related to regular expressions in the sense that they can be converted into each other. Thus, DFAs are often used to implement regular expression matchers.
Questions tagged [dfa]
569 questions
87
votes
3 answers
Design DFA accepting binary strings divisible by a number 'n'
I need to learn how to design a DFA such that given any number 'n', it accepts binary strings {0, 1} whose decimal equivalent number is divisible by 'n'.
There will be different DFAs for different 'n', but can somebody give a basic approach that I…
Naveen
- 1,193
- 4
- 13
- 17
50
votes
5 answers
DFA vs NFA engines: What is the difference in their capabilities and limitations?
I am looking for a non-technical explanation of the difference between DFA vs NFA engines, based on their capabilities and limitations.
blunders
- 3,619
- 10
- 43
- 65
31
votes
7 answers
How are finite automata implemented in code?
How does one implement a DFA or an NFA for that matter in Python code?
What are some good ways to do it in Python? Are they ever used in real world projects?
user5899005
- 451
- 1
- 4
- 5
30
votes
2 answers
Grammatical inference of regular expressions for given finite list of representative strings?
I'm working on analyzing a large public dataset with lots of verbose human-readable strings that were clearly generated by some regular (in the formal language theory sense) grammar.
It's not too hard to look at sets of these strings one by one to…
Stephen Lin
- 5,470
- 26
- 48
22
votes
4 answers
LR(1) Item DFA - Computing Lookaheads
I have trouble understanding how to compute the lookaheads for the LR(1)-items.
Lets say that I have this grammar:
S -> AB
A -> aAb | a
B -> d
A LR(1)-item is an LR(0) item with a lookahead. So we will get the following LR(0)-item for state 0:
S ->…
mrjasmin
- 1,230
- 6
- 21
- 37
18
votes
1 answer
Finding the complement of a DFA?
I am asked to show DFA diagram and RegEx for the complement of the RegEx (00 + 1)*. In the previous problem I had to prove that the complement of a DFA is closed and is a regular expression also, so I know that to convert a DFA, M to the complement,…
Matt Hintzke
- 7,744
- 16
- 55
- 113
16
votes
4 answers
Regular expressions Equivalence
Is there a way to find out if two arbitrary regular expressions are equivalent? Looks like complex problem to me, but there might be some DFA simplification mechanism or something?
amit
- 10,612
- 11
- 61
- 60
14
votes
2 answers
Is L = {a^n b^m | n>m} a regular or irregular language?
How can I prove if L = {a^n b^m | n>m} is a regular or irregular language?
Jerald James Capao
- 175
- 1
- 1
- 7
13
votes
1 answer
DFA construction in Knuth-Morris-Pratt algorithm
I am referring to the outline of the Knuth-Morris-Pratt (KMP) algorithm for substring search in Sedgewick's book "Algorithms" (4th ed.).
The KMP algorithm uses a backup in substring search based on a deterministic finite automaton (DFA). I…
madison54
- 743
- 2
- 8
- 19
13
votes
4 answers
Can a DFA have epsilon/lambda transitions?
Can´t find anything affirmative about it. And a NFA with any epsilon transition is a epsilon-NFA ?
Thanks.
liwing
- 211
- 2
- 3
- 8
12
votes
5 answers
Create set of all possible matches for a given regex
I'm wondering how to find a set of all matches to a given regex with a finite number of matches.
For example:
All of these example you can assume they start with ^ and end with $
`hello?` -> (hell, hello)
`[1-9][0-9]{0,3}` -> (1,2,3 ..., 9998,…
Kendall Hopkins
- 43,213
- 17
- 66
- 89
12
votes
1 answer
NFA/DFA implementation in C#
Does anyone know of any good NFA and DFA implementation in C#, possibly implementing as well conversions between both? What I would like would be to be able to construct a NFA and then convert it automatically to a DFA, but without having to write…
Miguel
- 3,466
- 8
- 38
- 67
11
votes
6 answers
Efficient algorithm for converting a character set into a nfa/dfa
I'm currently working on a scanner generator.
The generator already works fine. But when using character classes the algorithm gets very slow.
The scanner generator produces a scanner for UTF8 encoded files. The full range of characters (0x000000…
raisyn
- 4,514
- 9
- 36
- 55
11
votes
5 answers
DFA Based Regular Expression Engines for Java with Capture
Are there any (free) regular expression engines for Java, that can compile a regular expression to a DFA, and do group capturing while matching the DFA ?
I've found dk.brics.automaton and jrexx, which both compile to DFA, but neither seems to be…
Sami
- 3,263
- 3
- 29
- 37
10
votes
1 answer
How do you construct the union of two DFA's?
Does anyone have a straightforward description of the algorithm for constructing the union of two given DFA's? For example, say we have two DFA's over {0,1} where
{w|w has an odd number of characters}
w has states A and B
delta | 0 |…
Old McStopher
- 6,295
- 10
- 60
- 89