1 a)

The following is Finite State Automaton A:

(i) What are the first eight strings of L(A) if going by lexical order?

(ii) What are the first four strings of L(A) if going by dictionary order?

(iii) ConversionofthefinitestateautomatonAtoaregularexpression:

Add new initial and final states. If state 1 is removed first what is the resulting machine? If state 2 is removed first what is the resulting machine? If state 3 is removed first what is the resulting machine?

(iv) Write a regular grammar which defines the same language as finite state automaton A. Remember: a grammar is regular if each production is of the form: N -> t, or N -> tB, or N -> .

(b) Write a regular expression for each of the following languages:

(i) The language of all strings over {0, 1} which do not contain 00 as a substring

(ii) The language of all strings over {0, 1} which do not contain 101 as a substring

2 a) Write a context free grammar for the language {aibjak: i = j + k}, and show a right derivation for the string: aaaaabbaaa

b) i) Show that the grammar below is ambiguous. S -> S * S

S -> S + S

S -> num (ii) Write an unambiguous grammar to define the same language. Make sure that addition and multiplication

have the usual precedence (i.e. 2+3*4=14, not 20).

Answer A or B:

A) E -> E + T

E -> T

T -> T * F

T -> F

F -> num

B) E -> E * T

E -> T

T -> T + F

T -> F

F -> num

c)

Consider the grammar

S -> aS | aSbS |

(i) Show a derivation for aab

(ii) Show that the grammar is ambiguous.

d)

R-> R* | (R) | R+R|RR | letter is a grammar which recognises regular expressions.

Show a derivation for (ab + c)* where a,b,and c are recognised as letter. The grammar is ambiguous. Give an unambiguous grammar which recognises regular expressions, and which produces

derivation trees which correspond to the way in which regular expressions are interpreted.

3 0 0 2 0 3 0 0 2 0