1

I want to generate a regular expression by using only + (or, union), * (0 or more), and (^+ 1 or more) operations.

The language contains only 0 and 1. The problem is to generate a regular expression so that the words generated will contain 0(s) and the number of zeros will not be a multiple of 3. I generated the regular expression for the other case, i.e., the number of zeros is a multiple of 3 which is

1* + (1* 0 1* 0 1* 0 1*)*

How can I do the opposite of this?

Bilkent Ogrencisi
  • 15

1 Answers1

1

You want the number of zeros to be $3n+1$ or $3n+2$. That is, you want, say, a prefix with one or two zeros then a number of zeros that is a multiple of $3$.

A single zero: 1*01*

Two zeros: 1*01*01*

All in all:

((1*01*)+(1*01*01*))(1*01*01*01*)*

Jean-Claude Arbaut
  • 23,277