COS3701 Assignment 4 Yearly Module 2022 (Unique Number: 830436)

UnisaAssignHelp




COS3701
Assignment 4
Unique Number:
830436

, UnisaAssignHelp
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:

Read a go to state 1 – here we have 1 a and 0 bs so we have OE
Read b go to state 4 – OO
Read a go to state 2 – EO
Read a go to state 4 – OO
Read b go to state 1 – OE
Read b go to state 4 – OO
Read b go to state 1 – OE
Read a go to state 3 –EE
Read ∆ go to state halt

The TM will reject any word that is not in EVEN-EVEN.




2