Question

Let $\mathit{D}\mathbf{=}\{w|w$contains an even number of a’s and an odd number of b’s and does not contain the substring ab}. Give a DFA with five states that recognizes role="math" localid="1663218927815" $\mathit{D}$and a regular expression that generatesrole="math" localid="1663218933181" $\mathit{D}$.(Suggestion: Describe$\mathit{D}$ more simply.)

Short answer

The DFA with five states that recognizes $\mathit{D}$is as follows,

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

Step-by-step solution

Explain DFA

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.

Give a DFA with five states that recognizes   and a regular expression that generates   

Deterministic finite automata (or DFA) are state transition machines which approve or disapprove sequence by communicate of information and sequence. Suppose $M$have been the DFA that recognises the language $D$and has five states. $M$'sfollowing 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 width="9" height="15" role="math">b's (1) followed by an even number of a's (0). The language $D$ may written as a mixture of the two languages role="math" localid="1663218199506" $D_1\mathrm{and}{D}_2$ .

The regular language can be defined as follows,

Consider the two languages,

$$\begin{gathered} D_1=\left\{w|w \text{contain} \text{odd} \text{number} \text{of}\right.\left. b\text{'}s\right\} \\ {D}_2=\left\{w|w \text{contain} \text{even} \text{number} \text{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 $D_2$and the regular expression $R$ generates $D$.

The relation can be defined as,

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

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

role="math" localid="1663218795257" $$\begin{gathered} R=b\left(bb\right)*\bullet \left(aa\right)* \\ R=b\left(bb\right)*\left(aa\right)* \end{gathered}$$

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