1

Let Σ be {0, 1} Give a regular expression generating words over Σ containing an even number of 1’s or with a length which is multiple of 3.

I came up with this solution:

ε ( ((0*(10*10*)) + ((0+1) (0+1) (0+1)) )

and that's from this automata I drew up enter image description here

but I am unsure if it's correct...

Glorfindel
  • 3,955
Paul
  • 31

2 Answers2

0

I think in the even number of $1$'s category, your NFA will miss strings of the form $110$ since you do not have an ending $0*$ at the end of your regex.

The other part of your regex only detects strings of length $3$, not multiples of 3. The correct thing would be to allow the second part of your regex to be repeated as many times as you want.

So, doing this step-by-step:

  1. even number of ones: $\ (0^*(10^*)(10^*)0^*)^*$ The inner part of the regex allows for any number of zeroes before, after, and in between two $1$s. The outer $*$ allows for the two 1's matching regex to repeat as many times as desired, thereby allowing for an even number of 1's

  2. strings of lengths of multiples of 3: $((0 + 1)(0 + 1)(0 + 1))^*$ By allowing the entire chunk to repeat, we allow strings of length $\ 0, 3, \ldots, 3n, n \in \mathbb{N}$.

Full regex: $$R = ((0^*(10^*)(10^*)0^*)^*) + ((0 + 1)(0 + 1)(0 + 1))^*$$

Siddharth Bhat
  • 8,452
  • edited the regex to work for even number of zeroes – Siddharth Bhat Apr 29 '16 at 15:03
  • Thank you so much! , but do the regex also need to work for even number of zeros for the question? i mean is it right for this question also? – Paul Apr 29 '16 at 15:05
  • I'm not entirely sure what you mean, but the regex is a solution to your question if that's what you're asking. – Siddharth Bhat Apr 29 '16 at 15:09
  • @Paul - yes, it is definitely "inefficient" in the sense that there are some states that could be pruned. But, well, I think this is the most intuitive way to go about it. Efficiency is an exercise for the reader :) – Siddharth Bhat Apr 29 '16 at 15:09
0

Hint. Your language is the union of two (regular) languages: the langage $L_1$ of all words containing an even number of $1$'s and the language $L_2$ of the words of length multiple of 3. Now just find a regular expression for $L_1$ and a regular expression for $L_2$ (this is easy in both cases) and just take the union of your two regular expressions.

J.-E. Pin
  • 40,163