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.

And for my answer:

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

The second question is:

Construct a deterministic finite state automaton for recognising the numbers as described in Question 1

And my answer is:

Diagram of finite automaton

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 !

  • 1
    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
  • Good question, and +1 for asking for confirmation of your answers instead of asking for the answers. – Ross Patterson Jan 2 '13 at 12:13

No, your deterministic finite automaton is incorrect. Your regular expression is.

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.

Modelling optional values

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).

Modelling one or more times in a DFA

Applying those ideas to your Deterministic Finite Automaton, we get the following:

Deterministic Finite Automaton

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.

Non-deterministic Finite Automaton

  • 1
    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
  • 1
    Inkscape – meisterluk Dec 7 '13 at 10:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.