Question 1

This question is about finite-state automata (FSAs), and context-free grammars (CFGs). You are given the following automaton A over the alphabet Σ = {a, b, c}:

a, b

a

(a)  Give a formal definition (i.e. as a 5-tuple) of the above automaton A.

[5 marks]

(b)  Give two words contained in the language accepted by the automaton A, and two words not contained in the language accepted by the automaton A.

[2 marks]

(c)  Explain what makes the automaton A non-deterministic.

[2 marks]

(d)  Give, as transition graph, a deterministic FSA that accepts the same language as A. Justify your answer, for example by following the subset construction.

[8 marks]

(e)  Give, as transition graph, the minimal deterministic FSA accepting the same language as A.

Justify your answer, for example by building a marking table of necessarily distinct states. Make sure you show why each marked entry in the table gets marked.

[8 marks]

Question 2

This question is about regular expressions (REs) and finite-state automata (FSAs).

Notation: in the REs below, the Kleene star has higher precedence than sequencing; and sequencing has higher precedence than +. E.g. 10* 1 + 11* 1 = (1(0* )1) + (1(1* )1).

(a)  Consider the regular expression r:

b (ab + ba)* b

(i)  Which of the following words (by e we denote the empty word) belong to the language defined by r, and which do not?

e, bb, bab, baba, babbab

Briefly justify your answer, for example by explaining how the regular expression will accept (i.e. match) the words that belong to its language, and how it will not accept those that do not belong in it.

[5 marks]

(ii)  Give, as a transition graph, an FSA (possibly with e-transitions) recognising the same language as r .

Note: You should not use transitions with composite labels, e.g. of the form q1   q2 .

[5 marks]

(b)  Syntactically different regular expressions may represent the same language. Consider regular expressions over Σ = {a, b}. Which of the following equations hold?

1.   a + b = b + a

2.   (a + b)*  = a* + b*

3.   (a + b + ba)*  = (a + b + ab)*

Briefly justify your answers.                                                                                     [6 marks]

(c)  Consider the following languages over the alphabet {a, b, c}:

1.  The language of all words which contain at least one a, an arbitrary number of b’s and no c’s.

2.  The language of all words which start with a and have even length.

For each of the above languages, give an FSA or a regular expression that defines them.

You do not need to justify your answers.

[5 marks]

(d)  Let L be the language of all words over {a, b, c} which start with a and have even length. Give an FSA or a regular expression defining the complement language of L, i.e. the language of all words over {a, b, c} which do not belong in L.

Brieflyjustify your answer, i.e. explain why your FSA/RE accepts the complement language.

[4 marks]

Question 3

This question is about pushdown automata (PDAs) and context-free grammars (CFGs). (a)  You are given the following PDA A with Σ = {a, b, c} and Σst  = {$, 0}:

pop($)

(i)  Give three words accepted by the automaton A, and three words that are not accepted by A. Two of the accepted ones should contain at least one a.

[6 marks]

(ii)  For two of the three accepted words, give an accepting run.

[6 marks]

(iii)  Give a context-free grammar recognising the same language as the PDA A.

[3 marks]

(b)  Consider the following context-free grammar G over the alphabet Σ = {a, b, c}, where S is the start variable:

S  →  aXSb | ε | bX

X  →  XbX | c

(i)  Using the rules of the grammar G, give a derivation for the word bc.

[2 marks]

(ii)  Give a PDA recognising the same language as the grammar G.

Note: You can use the general method we saw in the lectures, or find the PDA by in- spection. Moreover, you can use composite-push transitions of the form push(x1 · · · xn ),

for n > 1.                                                                                                           [6 marks]

(iii)  Using the PDA you constructed in (ii) above, give an accepting run for the word bc.

[2 marks]