Peter Linz Edition 4 Exercise 3.1 Question 15 (Page No. 76)

Question

Find a regular expression for
$L =$ {$w∈ $ {$0,1$}$^* : w$ has exactly one pair of consecutive zeros} .

Answer 1

$Regular$ $Expression$ : $1^* (01^+)^*  00 (1^+ 0)^* 1^* $

• $1^*$: Your expression could start with any number of 1’s since there is no restriction on the number of 1’s. Since it is $1^*$, you can also start your Expression with 0 by taking $1^*$ as Epsilon(∊)
• $(01^+)^*$: If you find a $0$ then it should be followed by at least ‘one’ $1$ since you don’t want consecutive $0’s$
• $00$ : The one pair of consecutive $0’s$ you were looking for
• $(1^+0)^*$ : After you find the 00 you were looking for you cannot have another $0$ following it since then you’ll have a substring $000$ which equates to 2 consecutive $0’s$. So a 00 is always followed by at least ‘one’ $1$. After the $1$, if you encounter another 0 then that 0 again has to be followed by at least ‘one’ $1$. So , you will have a loop here of $(1^+ 0)$ again and again and hence we add star to $(1^+0)^*$ 
• $1^*$: Notice that if you end your $Regular$ $Expression$ with $(1^+ 0)^*$ , every one of your strings will end with 0 . So with $1^*$ at the end it can also produce all the strings in $L$ ending with 1