Help Keep Boards Alive. Support us by going ad free today. See here: https://subscriptions.boards.ie/.
If we do not hit our goal we will be forced to close the site.

Current status: https://keepboardsalive.com/

Annual subs are best for most impact. If you are still undecided on going Ad Free - you can also donate using the Paypal Donate option. All contribution helps. Thank you.

https://www.boards.ie/group/1878-subscribers-forum

Private Group for paid up members of Boards.ie. Join the club.

Regular expressions - odd amounts, as opposed to even

The_B_Man · 2011-10-30 15:14:26

Can someone answer this for me: Give a regular expression for "The set of all strings of 0's and 1's having an odd number of 0's". The input alphabet is obviously {0,1}. I understand the question, but I just don't know how to represent an odd amount of 0's in regular expression form. I could even draw a Finite State…

30-10-2011 04:14PM

#1

The_B_Man

Registered Users, Registered Users 2, Paid Member Posts: 8,000 ✭✭✭

Something about sandwiches

Join Date: March 2003

Posts: 7474

Can someone answer this for me:

Give a regular expression for "The set of all strings of 0's and 1's having an odd number of 0's".

The input alphabet is obviously {0,1}. I understand the question, but I just don't know how to represent an odd amount of 0's in regular expression form. I could even draw a Finite State Machine to represent it!

Any help appreciated.
Thanks.

0

Comments

#2 01-11-2011 12:00AM

humbert

Registered Users, Registered Users 2 Posts: 5,238 ✭✭✭

Join Date: September 2005

Posts: 5108

This looks like a sufficiently similar example. Although I only took a cursory glance at it.

I think the approach would be to create an expression to find pairs of 0s that may or may not be consecutive, then find 0 to infinitely many of them, and finally check to make sure that sequence is followed by a 0.

I'm sure there are other approaches.

0