2. A Turing machine can be conceptualised as consisting of an infinite tape, a read-write head, and memory. Based on this description, describe the key features of a Turing machine and how it operates. (25 marks)

3.Consider the language of all strings of symbols from the alphabet = {0,1} that have a length at least 3 and its third symbol is a 0.(25 marks)

a) Draw the finite state diagram of a deterministic finite automaton for .

b) Provide a regular expression corresponding to .

c) Provide a grammar (regular grammar or context-free grammar) corresponding to and transform it into Chomsky Normal Form.

4. (25 marks)

a) Construct a deterministic finite automat that recognises the language of all strings of symbols from the alphabet = {, } that do not contain the substring bab

b) Give both a regular expression and a context free grammar for the language of all strings of symbols from the alphabet = {, } that start and end with the same symbol

5.(25 marks)

a) Briefly describe the workings of a deterministic Turing machine that accepts {0n1 n }.

b) Draw a state diagram for the Turing machine from a).