Q 8. In this question we carry out some of the processes involved in establishing the fact that the languages described by DFAs, NFAs, regular expressions and regular grammars are all the same class, the regular languages.

(a) Give the state diagram of an NFA over {0, 1} recognising the language (01 + 00)∗ + 1. (You do not need to name the states in your diagram.)

(b) Let N be the NFA over {0, 1} shown below. Draw the state diagram of a DFA accepting the same language as N.

(c) Let M be the DFA over {0, 1} shown below.

(i) Give the regular grammar, H, corresponding to the DFA M.

(ii) Give a derivation for the word 10011 in the grammar H.

(d) Consider the regular grammar, G, with terminal symbols T = {0, 1}, non-terminal symbols N = {σ, A, B}, starting symbol σ, and production rules

(i) Draw the diagram of the NFA, N, corresponding to the regular grammar G.

(ii) Give an accepting computation of the word 0001 by N.

(iii) Write down a regular expression for the language L(G) generated by G.