CP50004E:Theory of Computation- IT Assignment Help

Element 1

Title: Written submission

Task details

Answer the following questions:

1. Consider the language L of all strings made of the symbols 0, 1 that every appearance of 0 is followed immediately by a 1.

a. Construct an FA whose language in L.

b. Give an RE for the language in L.

c. From the RE, build a Context-Free Grammar (CFG) for L and covert it to CNF.

d. From the FA, build a regular grammar for L.

2. Consider the following NFA with ? = {0, 1}

a. Covert the NFA to DFA.

b. Find the regular expression for the FA.

c. Explain in English the language accepted by the FA.

3. Consider the following CFG with starting variable S and ? = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}: S ? M U V U ? N | ? V ? V V | N N ? M | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 M ? 1 | 2

a. Create a derivation tree for your student number.

b. Is this grammar ambiguous or unambiguous? Briefly explain why.

c. Convert the CFG into Chomsky Normal Form.

4. Consider the language 0 x1 y0 y1 x for x, y ? 1 and the ? = {0, 1}:

a. Construct a Pushdown Automaton (PDA) that recognise the language.

b. Explain in your own words how this PDA recognises the language.

5. Draw and describe the following Touring Machines (TMs) as required:

a.Draw and describe a TM that copies the input string in reverse order, separating the first copy from the second copy by a special symbol. For example, if the input string on the tape is 1000, the TM should end with 1000$0001 on the tape.

b. Draw and describe a TM that computes the addition of two binary numbers. For example, if the input string on tape is 101$111, the TM should end with 1100 on the tape.