Menu
Write an expression that contains an even number of 0s or an odd number of 1s
I got it down to:
1*(01*01*)* + 0*10*(10*10*)* where the first part represents an even number of 0s and the second part an odd number of 1s
However, there's supposed to be a simplified solution that I'm not seeing. Any tips?
442
The expression +0+1 describes the strings with length zero or one, and the expression (0 + 1)*(00 + 10 + 11) describes the strings with length two or more. ¯ (c). All strings containing an even number of 0's: 1*+ (1*01*0)*1*.
(1*0)*11(1*0)*
But notice that strings containing only 1, i.e., no occurrence of 0's must be accepted by the automata because zero number of 0's is still acceptable since 0 is also an even number but this regex is declining 1∗ to be accepted. So we just take union with 1 and thus the final regex will be R=(1+1∗01∗01∗)∗.
Regular Expression (RE) for starting with 0 and ending with 1. RE for ending with b and having zero or multiple sets of aa and bb. A regular expression of the second last symbol is 1. RE for starting with 1 having zero or multiple even 1's.
Odd-1s part: 0*1(0|10*1)*
Even-0s part, depends:
(1|01*0)* (1|01*0)+ 1*(01*01*)+ (as in OP)old answer: correct under case 1 and 2
(1*(01*0)*)+ | 0*1(0*(10*1)*)* Kudos to @OGHaza for helpful comments.
182
Making use of the fact that even-length strings ALWAYS satisfy your constraints:
^(([01]{2})*|1*(01*01*)*)$ If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
