World's most popular travel blog for travel bloggers.

What language should the following DFA recognise?

, , No Comments
Problem Detail: 

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.

Asked By : user913923219
Answered By : collapsar

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback