COSC1107/1105 Computing Theory
School of Computing Technologies Semester 2, 2021
Tutorial No. 3: NFAs and DFAs
Before this tutorial you are expected to have read Section 4 of the Computing Theory notes.
The aim of this tutorial is to gain some experience in the analysis and design of finite state automata. By the end of this tutorial you should be able to trace a computation for a given string and DFA or NFA. You should also be able to generate an appropriate NFA or DFA from a specification.
PART1: FiniteStateAutomata………………………………………………………………….. Finite Automata are theoretical machines that read an input and either accept or reject that input. They consist of states and transitions between the states. When a symbol from the input is read, a transition from the current state is taken, possibly to another state, maybe back to the same state.
It is important to note the differences between non-deterministic finite automata (NFAs) and the determinitistic finite automata (DFAs). Deterministic simply means that there is never any choice for a given input; the transition to be taken for any input is extremely explicit. In our case, when in a particular state with a certain input there is only 1 transition that can be taken. Otherwise the machine isn’t deterministic. It should be evident that a machine that never has to make a decision would be easy to create.
Examples:
Give a regular expression and an equivalent NFA for the language over {a, b, c} that starts with aa and contains the substring ba.
Regular Expression : aa(a|b|c)∗ba(a|b|c)∗ An equivalent NFA and DFA is below.
q0
a, b, c b,c
q0
a q1 error
a q2
b q3 a q4
a,c b a,b,c
a,b,c a,b,c
b,c
a q1 a q2
b c
q3 a q4
From the above figures you will notice that the NFA is a lot simpler and intuitive to design from the regular expression. The DFA looks more complex. We will learn a mechanism for converting NFAs to DFAs later in this course. Notice in the DFA every state has defined a transition for every possible input. This is a requirement of a DFA. The state that indicates error is introduced to explicitly show the input that is rejected by this machine.
(a) Build an NFA that accepts the following languages (build a separate NFA for each).
1
COSC1107/1105 – Computing Theory Tutorial 3: NFAs and DFAs Page 2 of 5 i. Strings over the digits 0 − 9 which contain at least three 1s.
Solution:
0,2−9 0,2−9 0,2−9 0−9 q0 1 q1 1 q2 1 q3
0−9 0−9 0−9 0−9 q0 1 q1 1 q2 1 q3
ii. Strings over the digits 0 − 9 which contain 777 somewhere in the string.
iii. Strings over the digits 0 − 9 which do not contain 777 anywhere in the string.
iv. Strings over the digits 0 − 9 which have length 5 or less.
(b) Would any of these be harder or easier to do as a DFA?
(c) Give a regular expression that represents each of the following sets and build an equivalent NFA.
i. The set of strings over { a, b, c } in which all the as precede the bs, which in turn precede the cs.
ii. The set of strings over { a, b, c } that begin with an a, contain exactly two bs and end with cc. Solution: a(a | c)∗b(a | c)∗b(a | c)∗cc
Solution:
0-9 0-9 q0 7 q1 7 q2 7 q3
Solution:
0-6,8-9
0-6,8-9
q0 7 q1 7 q2 0-6,8-9
Solution:
q0 0-9 q1 0-9 q2 0-9 q3 0-9 q4 0-9 q5
Solution:
1. For languages requiring strict ordering e.g., (ab)∗ or three consecutive 1s the easier way is to construct a DFA as there may be only one way to generate the strings. See that, trivially, every DFA is also a NFA.
2. For languages that are expressed as union of languages (or could be conceptualised that way), easier way is to construct automatons for each of them separately and join with a lambda-transition. That is, build a NFA.
3. NFAs are generally smaller in size as compared to DFAs. Because of this, it may be practical to construct NFAs as opposed to DFAs.
Solution: a∗b∗c∗
abc
q0 λ q1 λ q2 λ qf
RMIT CT 2021 (Semester 2) – Exercise 1 continues on the next page. . .
COSC1107/1105 – Computing Theory Tutorial 3: NFAs and DFAs Page 3 of 5
a,c a,c a,c
q0 a q1 b q2 b q3 c q4 c qf
iii. The set of strings over { a, b, c } that do not contain the substring aa.
Solution:
((a | λ)(b | c)+)∗(a | λ)
or
((b | c)∗(a(b | c))∗)∗(a | λ) or
(b | c | ab | ac)∗(a | λ)
Possible DFA:
λ
q a,λ q b,c q
012
λ
b,c
q0 a q1 b,c
(d) Discuss amongst your group and draw the transition diagram for an “entry- code” machine (one of those machines next to some doors where you punch a four-digit number into it and it opens if you punch in the correct number). Assume that there are only five digits (0 − 4) and that the correct code is 1234. A string of digits should be accepted by your machine even if it’s more than four-digits long, so long as it contains the string 1234 somewhere inside it (i.e. it should accept 321312343213).
(e) RFC stands for Request For Comment. These are a body of documents about internet related issues. Each article has a number, of the form RF C − 1234 (the number changes for different documents). There is also a subset called FYI (For Your Information). Each FYI also has an RFC number. Simiarly there is a set of STD documents (which document technical standards). Build an NFA that will determine if the string is a valid identifier for an RFC. For example, it would accept the following strings:
RF C − 1234 F Y I − 0011 STD − 0054
Solution:
Solution:
0-4 0-4 q0 1 q1 2 q2 3 q3 4 qf
RMIT CT 2021 (Semester 2) –
Exercise 1 continues on the next page. . .
COSC1107/1105 – Computing Theory Tutorial 3: NFAs and DFAs Page 4 of 5
q0
q1 R q2 F q3 C q4 λλ
λ q5 F q6 Y q7 I q8 λ q13
λ
λ
−
q9
S q10 T q11 D q12
q 0−9q 0−9q 0−9q 0−9q 18 17 16 15 14
(f) There is a vending machine that sells chocolate bars. It sells “Chocos” for 50 cents and “Chewys” for 70 cents.
A finite automata needs to be written to show if enough money has been entered. It has 2 final states (labeled Chocos and Chewys) and an error state if too much money is entered. It accepts 10, 20 and 50 cent coins.
i. Is it easier to approach this problem with an NFA or a DFA? Why?
ii. Create a DFA to solve this problem.
Solution: There will be some variations here and it is going to be rather huge when drawn.
iii. How would you extend the machine you created in part (ii) to show how much change is required? Are there assumptions or limitations you need to create? (It is not necessary to build the complete machine that does this, but examples of sub sections of the machine will clearly demonstrate what you are indicating.)
Solution: NFA is always simpler, since DFA is subset of NFA. In this case, the only real difference is you only need to show the correct paths for the NFA, in the DFA you have to show every possible situation and error state.
Solution: Basically you’d need to create multiple different final states, one for each amount of change that could be given (up to 40c). Depending on which final state the machine is in, will determine the change given.
(g) The
• Astarnumbercommenceswith533,acometnumbercommenceswith544,andanasteroidnumbercommences
Astronomical Phones Company uses the following classification for telephone numbers:
with 512.
• An interplanetary number commences with 14, followed by at least 6 digits, none of which can be 9 or 0.
• An intergalactic number commences with 13, followed by at least 8 digits from {2, 3, 4, 5, 6}.
• A space station number commences with 555 followed by exactly one digit.
• A black hole number commences with 123, and must contain at least one 4.
• A distress number commences with 000 or 888.
• A deep space number commences with 9.
• Unless otherwise specified, a number commencing with 5 is a Starfleet number.
• Unless otherwise specified, a number commencing with 1, 2, 4, 6 or 8 is a Klingon number.
• All other numbers are erroneous.
i. Give an NFA to recognise and classify telephone number prefixes. You should have a distinct final state for each class of number.
ii. Estimate how many states will be required in an equivalent DFA.
iii. One day, the United Federation of Planets announces that in future, in addition to the above rules, all numbers
commencing with (42)n for n ≥ 1 are to be classified as answer numbers, and that all numbers of the form 4n2n for n ≥ 1 are to be classified as question numbers. Is it possible to extend your machine to incorporate these changes? If so, give reasons why (but there is no need to actually extend the machine); if not, give reasons why the extension cannot be done.
(h) Consider the language L = {w | w ∈ {0, 1}∗ } (that is, the language of all strings over 0 and 1 that end with 1). i. Build a NFA M1 such that L(M1) = L.
RMIT CT 2021 (Semester 2) – Exercise 1 continues on the next page. . .
COSC1107/1105 – Computing Theory Tutorial 3: NFAs and DFAs Page 5 of 5
Solution: The NFA is easy:
0,1
q0 1 q1
ii. Now, build an equivalent DFA M2, that is, one such that L(M2) = L(M1). M2 has to be deterministic.
Reflection:
For any given NFA, how large could an equivalent DFA become? For any given NFA, can you find a minimal equivalent DFA?
End of tutorial worksheet
Solution: The DFA is trickier:
01
q0 1 q1 0
RMIT CT 2021 (Semester 2) –