enter image description here My question is: what language should the following DFA recognise?

It seems that it should contain an odd number of substrings in the form 11*0. However, I am not sure whether there are any other conditions.


Arrive at the answer by following all paths from the start state to the accepting state identifying the 'tail recursion':

= 0*1*100*(1*100*1*100*)*
= 0*11*00*(11*00*11*00*)*

Intuitively, these are all strings over {0,1}* with an odd number of 10 substrings which is equivalent to the characterization you gave.

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.