Question 1 – Finite State Machines 1

Prove by construction that if the languages A and B are regular then the language that is the intersection of A and B is also regular. (5 Marks)

Question 2 – Finite State Machines 2

Design a deterministic finite state machine that recognises the language of all strings from the alphabet {0, 1, 2} that do not have two identical consecutive characters. For example, it should not recognise the strings 00 or 11 etc. Ensure that your design shows either a transition table or transition diagram, as well as a formal description of the          machine. (5 Marks)

Question 3 – Turing Machines 1

Design a Turing machine that accepts the set of strings with an equal number of 1’s and 0’s (in any mixed order). Include a high-level description of its algorithm and draw its transition diagram. (5 Marks)

Question 4 – Turing Machines 2

Show that a Turing machine is more powerful than a finite state machine by using an example language that is only decidable by a Turing machine. Provide a high-level   description of the Turing machine that decides this language. (5 Marks)

Question 5 – Lambda Calculus

Explain the concept of Church encoding in the context of Lambda Calculus and explain   how it is used to create the Church numerals. Use Church encoding to derive the Church numerals up to 4 and describe how they can be used to count in Lambda Calculus. (5 Marks)