CODEWITHSUNDEEP
regexpattern-matchingregular-languagefsmdfa
JackWM
JackWM

Reputation: 10545

Given a sequence of symbols, how to find the minimal DFA that can accept it?

For example: Given the below symbol sequence,

a b c b c d d d b c b c d d d d e

The simplest DFA that can accept it is a chain of 17 states.

While the below regular expression can derive the above sequence:

a (b c)* (d)* (b c)* (d)* e

And the corresponding minimal DFA has 8 states.

Further, the regular expression a ((b c)* (d)*)* e has even smaller minimal DFA with 4 states. And it can accept the example sequence.

In the above example, I only considers the * operator; More general, operator | can also be considered to reduce the DFA size.

So, the general question is:

Given a sequence of symbols, how to find the minimal DFA that can accept it?

Upvotes: 2

Views: 652

Answers (2)

antz
antz

Reputation: 1061

  1. Regular expression -> NFA
  2. Then NFA -> DFA
  3. Then DFA -> Minimal DFA

There are bunch of algorithms online that you can google for each step.
And you can check your DFA/NFA.
http://hackingoff.com/compilers/regular-expression-to-nfa-dfa

Upvotes: 2

nneonneo
nneonneo

Reputation: 179452

Easy. A DFA with one state can always do it. That one state is a start state, accepting state, and all symbol transitions loopback into it. That trivial DFA accepts all strings (∑*), and is definitely the smallest-possible DFA.

Upvotes: 2

Related Questions