AnGeL_555
November 25th, 2005, 07:37 AM
Hello all..
i want to write the regular expression for the following languages :
1) the set of all strings of 0's and 1's such that everypair of adjacent 0's appears before any pair of adjacent 1's.
2) the set of all strings of 0's and 1's whose number of 0's is divisible by five.
mehdi62b
November 27th, 2005, 05:03 PM
1) the set of all strings of 0's and 1's such that everypair of adjacent 0's appears before any pair of adjacent 1's.
2) the set of all strings of 0's and 1's whose number of 0's is divisible by five.about the first one,this one should work
0*[(100*)*]1*
about the second one I attched its DFA which you can write its expression
you should have 5 step for the remainings
0,1,2,3,4 which 0 is the accepting state,from every step if you recive 0 thayt means you should go to the step 2*a and if you recieve 1 you should go to 2a+1
for example in step 3 if you get 1,the remainder would be 2*3+1==2 so you go to state 2 if you recive 0,the remainer would be 2*3==1,you go to state 1.
(dashed lines mean 0 and solid lines mean 1)
mehdi62b
November 27th, 2005, 05:25 PM
sorry I misread the question,I thought you meant the number is divisible by 5 not the number of 0's2) the set of all strings of 0's and 1's whose number of 0's is divisible by five. the answer should be something like this,
1* [1* 0 1* 0 1* 0 1* 0 1* 0 1*]* 1*