QUESTION FIVE $(5)$

a$)$ Explain the Components and characteristics of a Deterministic Finite Automaton

b$)$ For the state diagram of the DFA $M$ below, give its formal definition as a $5-$tuple.QUESTION ONE $(1)$

a$)$ Explain the formal definition of a turing machine.

b$)$ With the following state diagrams of two DFAs, M$1$ and $M_2,$ Provide the solution the

questions about each of these machines.

i$.$ What is the start state?

ii$.$ What is the set of accept states?

iii. What sequence of states does the machine go through on input aabb $?$

iv$.$ Does the machine accept the string aabb $?$

v$.$ Does the machine accept the string $?$

QUESTION TWO $(2)$

a$)$ Outline the formal description of the machines $M_1$ and $M_2$ in OUESTION ONE $($b$)$

b$)$ Demonstrate the difference between the context$-$free language and the context$-$free

grammar.

QUESTION THREE $(3)$

a$)$ Assume that language $x$ is recognized by an NFA N$,$ and language $Y$ is the collection of

strings not accepted by some DFA M$.$ Show that $x=Y$ is a regular language.

b$)$ Outline the steps for generating a string of a language.

OUESTION FOUR $(4)$

a$)$ Explain the Chomsky normal form theorem.

b$)$ Show that if you add a finite set of strings to a regular language, the result is a regular

language.

c$)$ Show that if you add a finite set of strings to a nonregular language, the result is a

nonregular language.