COS3701 -
THEORETICAL
COMPUTER SCIENCE 3
ASSIGNMENT 4 - 2022
83046
, Solution
SELF ASSESSMENT ASSIGNMENT 04
Discussion
You have probably by now worked through all the prescribed work. We hope you have found the
course matter interesting. Please work carefully through our solutions and compare them to yours.
Note that if not otherwise indicated we assume that the alphabet is Σ = {a, b}.
Question 1
Chapter 23 – Problem 1(i), p. 562
Σ = {a, b}. EVEN-EVEN is defined on page 236 of Cohen: EVEN-EVEN = all strings x with an
even number of as and an even number of bs.
Note that TL101 refers to ODDPALINDROME but the language we are actually interested in is
EVEN-EVEN.
A TM that accepts this language is illustrated in Figure 1.
This TM has essentially four states
State 1 This represents the case where an odd number of as and an even number of bs have
been read (OE).
State 2 This represents the case where an even number of as and an odd number of bs have
been read (EO).
State 3 This represents the case where an even number of as and an even number of bs have
been read (EE).
State 4 This represents the case where an odd number of as and an odd number of bs have been
read (OO).
Consider the string aa. In this case the TM moves to state 1 after reading the first a (OE) and then
to state 3 after reading the second a (EE). The TM will then go the halt state and even number of
as (2) and an even number of bs (0) have been read.
Consider a more complicated string abaabbba. In this case the word is in EVEN-EVEN so the TM
should reach the halt state. What happens is:
2
THEORETICAL
COMPUTER SCIENCE 3
ASSIGNMENT 4 - 2022
83046
, Solution
SELF ASSESSMENT ASSIGNMENT 04
Discussion
You have probably by now worked through all the prescribed work. We hope you have found the
course matter interesting. Please work carefully through our solutions and compare them to yours.
Note that if not otherwise indicated we assume that the alphabet is Σ = {a, b}.
Question 1
Chapter 23 – Problem 1(i), p. 562
Σ = {a, b}. EVEN-EVEN is defined on page 236 of Cohen: EVEN-EVEN = all strings x with an
even number of as and an even number of bs.
Note that TL101 refers to ODDPALINDROME but the language we are actually interested in is
EVEN-EVEN.
A TM that accepts this language is illustrated in Figure 1.
This TM has essentially four states
State 1 This represents the case where an odd number of as and an even number of bs have
been read (OE).
State 2 This represents the case where an even number of as and an odd number of bs have
been read (EO).
State 3 This represents the case where an even number of as and an even number of bs have
been read (EE).
State 4 This represents the case where an odd number of as and an odd number of bs have been
read (OO).
Consider the string aa. In this case the TM moves to state 1 after reading the first a (OE) and then
to state 3 after reading the second a (EE). The TM will then go the halt state and even number of
as (2) and an even number of bs (0) have been read.
Consider a more complicated string abaabbba. In this case the word is in EVEN-EVEN so the TM
should reach the halt state. What happens is:
2
