# Constructing a Deterministic Finite State Automaton for a given Regex

I have a couple of exam questions for my compilers class and wanted to check if my solutions are correct.

The first question is:

Consider a language in which numbers start with an optional minus sign, followed by one or more decimal digits, followed by an optional decimal point. If the number contains a decimal point it is followed by one or more further decimal digits. Express the syntax of numbers in this language as a regular expression.

("-")? ["0"-"9"]+ ("."["0"-"9"]+)?

The second question is:

Construct a deterministic ﬁnite state automaton for recognising the numbers as described in Question 1 Where state 2,4,5 and 6 are terminals.

Are these solutions correct? I am unsure of what the DFA should look like and it's differences to an NFA.

Thanks !

• pst 2 and 4 can be the same state, also that is a DFA if you add a non-terminal "sink state" that accepts all transitions not defined in your solution and loops to itself for all cases – ratchet freak Jan 1 '13 at 19:15

The problem in your DFA is the declaration of 5 and 6 to be terminal nodes. A testcase such as "0." will be accepted by your DFA even though it should not.

# Optional values

I want to point out how you can model a general structure which includes optional values. Let's take for example a regular expression like "a?b". The idea now is to create two branches. One includes the optional element "a" and the other one excludes it. The inclusion branch merges with the other one with the first value that is obligatory again. # One time or more

As a second idea: How do we model quantities such as "once or more times"? We have to create an edge which requires us to read the symbol "a" one time. After that we create a self-loop which reads the symbol as many times as necessary (possibly zero). Applying those ideas to your Deterministic Finite Automaton, we get the following: # Non-deterministic Finite Automatons

An automaton becomes non-deterministic if there are two edges with the same label starting at the same vertex. In the example below starting with vertex "4" and reading the input "0", you won't know which path will accept the input string (left or down) and will proceed non-deterministically. • In the second diagram (the correct DFA), what notation is used to indicate that the dot "." path (from 3 to 4) can only be taken once? – rwong Jan 1 '13 at 19:49
• @rwong None, that's an error in my DFA. Thank you for pointing it out. I fixed it. – meisterluk Jan 1 '13 at 19:58
• Off-topic, what tool did you use to make those diagrams? – greenoldman Dec 6 '13 at 13:55
• Inkscape – meisterluk Dec 7 '13 at 10:05