T Naughton, NUIM
Back to CS355 home

Lab sheet 1 - Programming finite automata

In this lab, you will program some finite automata. We will use Paul Ming's Perl-based Virtual Turing Machine (VTM) to simulate each finite automaton (FA). You do not have to understand anything about a Turing machine for this lab.

Form into teams of two persons to each machine for this lab. This lab will be graded. Grading will be performed after 90 minutes by randomly picking one of the team members and asking them to construct an unseen FA in 10 minutes (without the help of other team members). The unseen FA will be of average difficulty in relation to the other problems in this lab sheet. Every member on the team receives the grade this person achieves. This procedure is designed to encourage peer-teaching in laboratories.

Below are two examples of how to simulate a FA using this system, followed by some problems. Before you leave, make sure a demonstrator checks your work.

Machine 1.A Construct a FA using the VTM that accepts the language L = {w : w{a,b}*, w ends with an a}. One possible solution is a FA M written formally as M = (Q, , , q₀, F) = ({00, 99}, {a, b}, {((00, a), 99), ((00, b), 00), ((99, a), 99), ((99, b), 00)}, 00, {99}). The function could be formatted equivalently as

Q\ |  a  b
-----------
 00 | 99 00
 99 | 99 00

or formatted equivalently as

 Q |  | (Q,)
---------------
00 | a |  99
00 | b |  00
99 | a |  99
99 | b |  00

When we rewrite this FA for the VTM we get the following table:

#Si,R, Sf, W, M
#--------------
00, a, 99, a, R
00, b, 00, b, R
99, a, 99, a, R
99, b, 00, b, R

To execute this FA, copy the table into the VTM, enter `00' as the starting state, enter `_' as the blank symbol, and enter an input word with three `_' symbols on each side. If, when it is run, the TM halts in an accepting state then we conclude that the word has been accepted.

Satisfy yourself that the FA is correct by testing it with three carefully chosen words that it should accept and three that it should not accept. In particular, should e (specified by supplying six `_' symbols as input) be accepted?

The following conventions have been applied in this example (you should adopt these conventions too):
(i) all non-accepting states will be labelled 00,01,02,... ,
(ii) all accepting states will be labelled 99,98,97,... , and
(iii) the symbol `_' is chosen as the blank symbol.

Machine 1.B Construct a FA using the VTM that accepts the language L = {w : w{0,1}*, w begins with a 1}. One possible solution is a finite automaton M written formally as M = {Q, , , q₀, F} = {{00, 01, 99}, {0, 1}, {((00, 0), 01), ((00, 1), 99), ((01, 0), 01), ((01, 1), 01), ((99, 0), 99), ((99, 1), 99)}, 00, {99}}. The function could be formatted equivalently as

Q\ |  0  1
-----------
 00 | 01 99
 01 | 01 01
 99 | 99 99

When we reqrite this FA for the VTM we get the following table:

#Si,R, Sf, W, M
#--------------
00, 0, 01, 0, R
00, 1, 99, 1, R
01, 0, 01, 0, R
01, 1, 01, 1, R
99, 0, 99, 0, R
99, 1, 99, 1, R

Machine 1.1 Construct a FA using the VTM that accepts the language L = {w : w{a,b}*, w contains the substring aa}.

Machine 1.2 Construct a FA using the VTM that accepts the language L = {w : w{0,1}*, w contains no 0s}.

Machine 1.3 Construct a FA using the VTM that accepts the language L = {w : w{0,1}*, w does not begin with a 1}.

Machine 1.4 Construct a FA using the VTM that accepts the language L = {w : w{a,b}*, w contains the substring baa but does not contain it at the very beginning of the word}.

Machine 1.5 Construct a FA using the VTM that accepts the language L = {w : w{0,1}*, w contains at least one 0, w contains an even number of 1s}. Note: zero is an even number.

Machine 1.6 Construct a FA using the VTM that accepts the language L = {w : w{a,b}*, w ends with the substring baa}.