Finite Automata, Regular Expressions, Context-Free Grammar, and Turing Machines

Question 1: L

Extensions will only be granted in exceptional circumstances. Documentary evidence will be required. Extensions must be agreed before the deadline. A student who fails to submit course work or dissertation by the applicable deadline shall be deemed to have failed to submit to assessment.

1. Understand the concepts and applications of finite automata

2. Understand and reason about the concepts of language grammars, and regular expressions in computer programming

3. Use computational complexity theories such as P, NP and NP -Complete to analyse the efficiency of algorithms

Answer the following questions:

1. Consider the language L of all strings made of the symbols a, b that have at least length of three symbols and whose first and last symbols are different.

a. [10 marks] Construct an FA whose language in L.

b. [6 marks] Give an RE for the language in L.

c. [6 marks] From the RE, build a Context-Free Grammar (CFG) for L.

d. [6 marks] From the FA, build a regular grammar for L.

2. For the language L {0,1}, find a regular expression representing the following:

a. [6 marks] All strings that do not begin with 11

b. [6 marks] All strings that every appearance of 0 is followed directly by a 1.

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. [5 marks] Create a derivation tree for your student number.

b. [5 marks] Is this grammar ambiguous or unambiguous? Briefly explain why.

c. [10 marks] Convert the CFG into Chomsky Normal Form. 4.

4. Consider the following Pushdown Automaton (PDA), which recognises palindromes and where s stands for any alphanumeric symbol:

a. [5 marks] Explain in your own words how it recognises palindromes.

b. [5 marks] Would this PDA accept your first name (as printed on your student ID) as input? Explain why or why not and how it would fail or

succeed.

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

a. [10 marks] Draw a TM that copy the input string in a reverse order, separating the first copy from the second copy by a special symbol for example the input string on tape is 1000, the TM should end with 1000$0001.

b. [10 marks] Draw a TM that compute the addition of two binary numbers, for example the input string on tape is 101$111, the TM should end with 1100

c. [10 marks] Describe in your own words how TM works in section b (TM that compute the addition of two binary numbers).

For full marks, provide complete, effective and efficient solutions.