theory regular langauge

Question

Write a regular expression for all strings of 0’s and 1’s in which there is an even number of 0’s between any two 1’s.

Comments

0^*(1(00)^+1)^*0^*

---

@Aditya_

it cannot generate 11.

Answer 1

$(0^{*} + 1(00)^{*}1)^{*}$  + $0^{*}10^{*}$

Comments

Wouldn’t this also generate 101

---

DevUt

check now.

---

It can still generate 11011

---

DevUt

ohh yes, how you approached.?

Answer 2

$0^{*}(1(00 + 1)^{*} (0 + \epsilon ) + \epsilon)$

Answer 3

Here is a regular expression that will match all strings of 0's and 1's in which there is an even number of 0's between any two 1's:

^(1(00)*1)*$

 

Explanation:

• ^ and $ anchor the regular expression to the start and end of the string, respectively. This ensures that the regular expression will only match the entire string and not just a substring.

• 1 matches the character 1.

• (00)* matches zero or more occurrences of the characters 00. This matches an even number of 0's.

• (1(00)*1)* matches zero or more occurrences of a 1 followed by an even number of 0's followed by a 1. This ensures that there is an even number of 0's between any two 1's.
  
   

  For example, this regular expression would match the following strings:

• 1
• 11
• 10001
• 10010001

• And it would not match the following strings:

• 0
• 10
• 101
• 1001
• 1000101
•  
• 100010001