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:
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 !
2
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.
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.
4