Elysian Shadows

Not technically a programming question since this is a theoretical CS question, but sort of relevant.

I need to give a regular expression for a language that contains an odd number of 1's or exactly two 0's. The alphabet is {0, 1}.

Here's my attempt, idk if this is correct or not.

(1* 0 1* 0 1*) OR ( (0* 1 0* 1 0*)* 1 (0* 1 0* 1 0*)* )

Can anyone help me out? I'm new to this and could use some help getting on the right track.

X Abstract X wrote:Not technically a programming question since this is a theoretical CS question, but sort of relevant.

I need to give a regular expression for a language that contains an odd number of 1's or exactly two 2's. The alphabet is {0, 1}.

Here's my attempt, idk if this is correct or not.

(1* 0 1* 0 1*) OR ( (0* 1 0* 1 0*)* 1 (0* 1 0* 1 0*)* )

Can anyone help me out? I'm new to this and could use some help getting on the right track.

I'm trying really hard to read this, but with all the 1's 2's and 0's it's hard to see what you're asking.

What do you mean you have to "give" a regular expression for a language? What are you trying to match exactly? And is there any 2's or is it just a 0 and a 1 for the language?

I'm not really sure what you're asking. Could you explain "for a language that contains and odd number of 1's or exactly two 2's. The alphabet is {0, 1}."?

Try providing us with some examples of what you'd like to be matched by the regular expression, and what you don't want to match.

I think he's in one of those way-the-fuck-too-abstract CS classes and is assuming that what he is doing is some sort of standard CS question... but it's not. =/

And I can't make heads or tails from the grammar/syntax of your "regular expression."

X Abstract X wrote:Not technically a programming question since this is a theoretical CS question, but sort of relevant.

I need to give a regular expression for a language that contains an odd number of 1's or exactly two 2's. The alphabet is {0, 1}.

Here's my attempt, idk if this is correct or not.

(1* 0 1* 0 1*) OR ( (0* 1 0* 1 0*)* 1 (0* 1 0* 1 0*)* )

Can anyone help me out? I'm new to this and could use some help getting on the right track.

I took a very similar class this summer, "Theory of Computation", class can go bite itself. However as it stands you have written a contradiction, sort of. If Sigma = {0, 1} then it not feasible two have any 2's, let alone exactly two 2's. I assume you meant something else?

However the set of possible answers would include:
1, 01, 10, 010, 001, 100, ... (thus the pattern we want to match is (0*10*)*

But we don't want to match an even number of one's, so we can't match the following pattern:
01010, 1010, 0110, 110, 11, 011, ... (thus the pattern we don't want to match is (0*10*10*)*

Unfortunately this approach isn't very helpful in finding the regex we desire in all cases. However, a DFA is. I'm going on the assumption that your class is similarly designed to mine, if not post back and I'll explain in more detail. I came up with the following DFA (for your given requirements, ignoring the "exactly two 2's")


Notice the '+' means OR. Also notice that the regex handles the case of just one 1, as well as every odd case beyond just 1. Ignore all the scratch work, the regex I believe you want is the one in red.

edit: whoops, I forgot a zero.. the regex you really want is
R = 0*10* + 0*10*(0*10*1)*

Wheeeeeeeeeeeeeeeeeeeeeeeeeeeeeell!!!!!

He blinded me with science...

Wow.

Gah, I meant to write exactly two 0's. Thanks for all the replies, I skimmed them and short seems to know exactly what I'm talking about. Gonna read your reply in more detail and reply back. The class I'm in is also called Theory of Computation.

Edit: Thank you very much short! The key is to construct the DFA instead of trying to reason through it in my head :P

I can't quite seem to get the same answer as short, but if I'm looking at this correctly, the right regex is: This is for the whole problem, including the "or exactly 2 zeros".

I don't have time to go back and do the work again, but it seems like you figured it out. Glad to help!!

Yep, thanks short. You're example was great, showed me how to use a DFA to get my regex :D

Ginto, that's the same answer that I got

I have no clue what the hell just happened in this topic. I'm just glad Short is a psychic savant. If these forums had a reputation rating, he would have just gained a lot of it.

dandymcgee wrote:I have no clue what the hell just happened in this topic. I'm just glad Short is a psychic savant. If these forums had a reputation rating, he would have just gained a lot of it.

+1 Reputation

k1net1k wrote:

dandymcgee wrote:I have no clue what the hell just happened in this topic. I'm just glad Short is a psychic savant. If these forums had a reputation rating, he would have just gained a lot of it.

+1 Reputation

lol don't make me blush. I do think psychic savant would make an awesome forum title...

short wrote:

k1net1k wrote:

dandymcgee wrote:I have no clue what the hell just happened in this topic. I'm just glad Short is a psychic savant. If these forums had a reputation rating, he would have just gained a lot of it.

+1 Reputation

lol don't make me blush. I do think psychic savant would make an awesome forum title...