0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

  0*1+0+(1+0+1+0+)*
= 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.

$\endgroup$

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