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




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 q0, the number of ‘b’ is always even that’s why we assign r = 0 at q0 state.

But at q1 number of ‘b’ is always odd that’s why we assign r = 1q1 state.


q1 is the final state because the machine is for odd ‘b’


 Regular Expression from machine RE1 = (a + ba*b)ba*


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 RE2 = (a* ba* ba*)a* ba*