How do you construct a DFA from a language that has a + sign? e.g. $L = \{(a+b)\}*$
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Did you mean the language $(a+b)*$, rather than $\{(a+b)\}*$? $\endgroup$– D.W. ♦Aug 5, 2013 at 4:13
-
$\begingroup$ There is a standard construction; have you read any material on the topic before posting here? What have you tried? $\endgroup$– Raphael ♦Aug 5, 2013 at 8:26
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
In this case + stands for the OR-operation. So the automaton is indifferent using an $a$ transition or a $b$ transition.
It's sufficient to construct an automaton with one state which is initial and final state and having one transition labeled with a, b.
-
$\begingroup$ If your alphabet is larger than just $\{a,b\}$, you should also add a garbage state with all letters other than $a$ and $b$ making a transition from the main state to the garbage state and all letters (including $a$ and $b$) sending the garbage state to itself. $\endgroup$– minarAug 6, 2013 at 11:39
$\begingroup$
$\endgroup$
It looks like your language is specified as a regular expression. (Regular expressions are allowed to contain the + and * operators.)
So, in general, you can use the following procedure:
Convert the regular expression to a NFA. There are standard methods for this; for instance, Thompson's algorithm is perhaps the best-known. See Russ Cox's explanation for a great tutorial.
Convert the NFA to a DFA. Again, there are standard algorithms for this task as well: namely, the subset construction, where you have one state in the DFA for each possible subset of states of the NFA.
All of this should be covered in standard sources, e.g., Wikipedia or an automata theory book. In the future, please go check those standard sources and do a bit of research on your own before asking here, to comply with this sites' expectations.
