T Naughton, NUIM
Back to CS355 home

Lab sheet 7 - Turing machine programming

In this lab you will program Turing machines (TMs). Students who have seen TMs before last week's lab (3CSSE,4Science,4CSSE,2MCompSci) can skip Section A. The remaining students (3Science,1MCompSci) must complete Section A before moving on to Section B. If you do not finish this lab sheet in this scheduled lab, you must complete it in your own time.

Your TMs will conform to the definition given in lectures (e.g. they will have a single accept state and a single reject state). Let 00 bet the start state, let 99 be the accept state, and let 50 be the reject state.

We will use Paul Ming's Perl Virtual Turing Machine (VTM). Read the information on Lab sheet 6 to refresh your memory of how the VTM works and to learn what conventions will be used in this lab (e.g. '_' is the blank symbol and you must place three of these on either side of your input).

Definition. A machine accepts a language if it goes into an accept state if it gets a word in that language and does not go into an accept state if it gets a word not in that language.

Definition. A machine decides a language if it goes into an accept state if it gets a word in that language and goes into a reject state if it gets a word not in that language.

Section A

Machine 7A.1 Construct a TM that accepts the language L_A1 of words containing zero or more a symbols and no other symbols. Only symbols a and b are permitted as input. More formally, this language could be written as L_A1={e, a, aa, aaa,...} or as L_A1={w : w {a,b}*, w contains zero bs}. To accept this language, the TM must halt in the accept state when it gets a word in the language. It does not matter what the TM does in response to an input that is not a word in L_A1 (i.e. it is perfectly respectable for the TM to crash or to run forever if it is presented with the input word aab, for example) as long as it doesn't halt in an accept state if it is ever presented with a word that is not in L_A1.

Machine 7A.2 Construct a TM that decides language L_A1. Here, the TM must halt in either the accept state of the reject state.

Machine 7A.3 Construct a TM that accepts the language L_A2 = {w : w {a,b}*, w contains the substring aab}.

Machine 7A.4 Construct a TM that decides language L_A2.

Machine 7A.5 Construct a TM that decides the language L_A3 = {w : w {a,b}*, w ends with an a}.

Machine 7A.6 Construct a TM that decides the language L_A4 = {w : w {a,b}*, w contains at least one a}.

Section B

Machine 7B.1 Construct a TM that accepts the language L_B1 of words containing some as followed by some bs. Only symbols a and b are permitted as input. More formally, this language could be written as L_B1={e, a, b, aa, ab,...} or as L_B1={a^mbⁿ : m,n >= 0}. To accept this language, the TM must halt in the accept state when it gets a word in the language. It does not matter what the TM does in response to an input that is not a word in L_B1 (i.e. it is perfectly respectable for the TM to crash or to run forever if it is presented with the input word aaba, for example) as long as it doesn't halt in an accept state if it is ever presented with a word that is not in L_B1.

Machine 7B.2 Construct a TM that decides language L_B1. Here, the TM must halt in either the accept state of the reject state.

Machine 7B.3 Construct a TM that accepts the language L_B2 = {aⁿbⁿ : n >= 0}.

Machine 7B.4 Construct a TM that decides language L_B2.

Machine 7B.5 Construct a TM that decides the language L_B3={ww^R : w {a,b}*}.

Machine 7B.6 Construct a TM that decides the language L_B4={w : w {a,b}*, w = w^R}. (These are the words over {a,b} that are palindromes; they read the same forwards as backwards.)

Machine 7B.7 Construct a TM that decides the language L_B5={w : w {a,b}*, w contains an equal number of as and bs}.

Machine 7B.8 Construct a TM that decides the language L_B6={w : w {a,b}*, w does not contain an equal number of as and bs}.

Machine 7B.9 Construct a TM that decides the language L_B7={ww : w {a,b}*}.