Let $D=\left\{w|w\right.$contains an even number of ’s and an odd number of ’s and does not contain the substring ab}. Give a DFA with five states that recognizes Dand a regular expression that generates D.(Suggestion: Describe Dmore simply.)

Deterministic finite automata (or DFA) are state transition machines which approve or disapprove sequence by interpreting them through a sequence that really is distinctive towards each packet. Each string, and so therefore every state sequence, is unique, as the name "deterministic" implies.

Deterministic finite automata (or DFA) are state transition machines which approve or disapprove sequence by communicate of information and sequence.Suppose have been the DFA that recognizes the language D and has five states. M's following example looks like this:

Sequence such as $\left\{b,baa,bbbaaaa,...\right\}$The language accepts the word b since it has an odd number of b's (1) followed by an even number of 's (0). The language D may written as a mixture of the two languages $D_1$and $D_2$.

The regular language can be defined as follows,

Consider the two languages,

$$\begin{gathered} D_1=\left\{w|w \mathrm{contain} \mathrm{odd} \mathrm{number} \mathrm{of} b\text{'}s\right\} \\ {D}_2=\left\{w|w \mathrm{contain} \mathrm{even} \mathrm{number} \mathrm{of} a\text{'}s\right\} \end{gathered}$$

The relation of the languages can be defined as follows,

$D=D_1\bullet D_2$.

Consider that, the regular expression $R_1$that generates $D_1$, the regular expression$R_2$generates and the regular expression R generates D.

The relation can be defined as,

$$\begin{gathered} R=R_1\bullet R_2 \\ \begin{array}{l}{R}_1=b\left(bb\right)*\\ R_2=\left(aa\right)*\end{array} \end{gathered}$$

Substitute, $R_1,R_2$in$R=R_1\bullet R_2$as follows,

$\begin{array}{l}R=b\left(bb\right)*\bullet \left(aa\right)*\\ R=b\left(bb\right)*\left(aa\right)*\end{array}$

Therefore, the regular expression that generates the language D is $b\left(bb\right)*\left(aa\right)*$.