CS370 - Computation and Complexity
Department of Computer Science
National University of Ireland, Maynooth
CS370 - Computation and Complexity
Department of Computer Science
National University of Ireland, Maynooth
T Naughton, NUIM
Back to CS370 home
Lab 3 - Turing machine programming (continued)
Here you will build on what you learnt in the previous lab about TM programming. Once again, we will use Paul Ming's Perl VTM . If you have not solved all of the problems on the previous sheet, you must do them first.
Machine 3.1 Construct a TM that decides the language L1={w : w 
{a,b}*, w does not contain an equal number of as and bs}.
Machine 3.2 Construct a TM that decides the language L2={w : w {a,b}*, w contains twice as many as as bs}.
Machine 3.3 Construct a TM that decides the language L3={anbnan : n 
0}.
Machine 3.4 Construct a TM that decides the language L4={wxw : w {a,b}*}. (Note, x is not defined so, rather than being a variable, it simply represents the symbol `x'. Note, also, that although w is a variable with a different value for each word, within each word it will have a single value; this means that in every word in this language there is an identical string on each side of the x.)
Machine 3.5 Construct a TM that decides the language L5={ww : w {a,b}*}.