T Naughton, NUIM
Back to SE307 home

Lab 4 - Machines simulating machines (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). To do this, each row in the TM's table of behaviour will have the following properties:
(i) the read and write symbols will be identical, and
(ii) the movement will always be `R'.
Below are two examples, followed by some problems. If you finish early, make sure you have completed every question in the previous lab sheets. You will have a lab exam next week on all the SE307 material covered to date. This lab exam will be worth between 25% and 50% of your continuous assesment mark for SE307.

Machine 4.A Construct a FA, embedded in a TM, that accepts the language L = {w : wÎ{a,b}*, w ends with an a}. One possible solution is a finite automaton M written formally as M = (Q, S, d, q₀, F) = ({00, 99}, {a, b}, {((00, a), 99), ((00, b), 00), ((99, a), 99), ((99, b), 00)}, 00, {99}). The function d could be formatted equivalently as

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

or formatted equivalently as

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

When we embed this FA in a TM we get the following table of behaviour:

#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 and 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.

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 4.B Construct a FA, embedded in a TM, 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, S, d, 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 d could be formatted equivalently as

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

When we embed this FA in a TM we get the following table of behaviour:

#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 4.1 Construct a FA, embedded in a TM, that accepts the language L = {w : wÎ{0,1}*, w contains no 0s}.

Machine 4.2 Construct a FA, embedded in a TM, 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 4.3 Construct a FA, embedded in a TM, 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 4.4 Construct a FA, embedded in a TM, that accepts the language L = {w : wÎ{a,b}*, w ends with the substring baa}.