FOR FREE CONTENT

Design a machine of the following language: L = Containing odd b where ∑ = {a, b}

Answer:

Here L = {b, bbb, ab, ba, ……}

As per the question,

Here r indicates remainder when the number of ‘b’ is odd, the remainder is one i.e. r = 1 otherwise remainder is zero i.e. r = 0 (when the number of ‘b’ is even).

At ${\mathit{q}}_{\mathbf{0}}$, the number of ‘b’ is always even that’s why we assign r = 0 at ${\mathit{q}}_{\mathbf{0}}$ state.

But at ${\mathit{q}}_{\mathbf{1}}$ number of ‘b’ is always odd that’s why we assign r = 1 a ${\mathit{q}}_{\mathbf{1}}$ state.

${\mathit{q}}_{\mathbf{1}}$ is the final state because the machine is for odd ‘b’. 

 Regular Expression from machine $\mathit{R}{\mathit{E}}_{\mathbf{1}}\mathbf{ }\mathbf{=}\mathbf{ }\mathbf{(}\mathit{a}\mathbf{ }\mathbf{+}\mathbf{ }\mathit{b}\mathit{a}\mathbf{*}\mathit{b}\mathbf{)}\mathit{b}\mathit{a}\mathbf{*}$

We can write another regular expression for

We can get odd numbers of b if we add one b at any even of b’s string. So, we first write regular expression for even number of  b’s then odd one b.

Regular Expression for even number of  b’s RE= (a*ba*ba*)* 

Now we add one b to make it odd $\mathit{R}{\mathit{E}}_{\mathbf{2}}\mathbf{ }\mathbf{=}\mathbf{ }\mathbf{(}\mathit{a}\mathbf{*}\mathbf{ }\mathit{b}\mathit{a}\mathbf{*}\mathbf{ }\mathit{b}\mathit{a}\mathbf{*}\mathbf{)}\mathit{a}\mathbf{*}\mathbf{ }\mathit{b}\mathit{a}\mathbf{*}$