[Solved]: Draw a graph of DFA for a regular language

Problem Detail: 

I'm trying to draw a DFA graph for the regular language where every chain:

* consists of symbols from the set {1,a,b}.  * starts with the subchain '1a'. * includes at least one subchain 'aa'. 

Output chains: $1aa, 1abaa, 1aaba, 1aaa, 1aaab, 1aab1a, \space ..., \space etc.$

There's no problem with checking the $'1a'$ subchain, but there's a problem with the double repeating action for an $'a'$ terminal in any part of the chain for getting at least one $'aa'$ subchain. The shortest chain here is $'1aa'$ and graph states change from $q_0$ to $q_3$ (which will possibly be the DFA's end state). If I draw a $(1,b)$-cycle for the $q_2$ state, the DFA might come to the end state $q_3$ on reading the wrong chain like $1aba$. From the other side, my DFA will only allow chains starting from $1aa$ (not $1a$) and that is not correct either.

My attempts leaded to this:

What should I correct here to add "at least one $'aa'$ check" feature? Or offer your version of this DFA graph.

Asked By : Happy Torturer

Answered By : sai_preet

$T$ is a 'trap state' $q_3$ is final accepting state. From state $T$ all inputs $a$, $b$, $1$ will direct to $T$ itself. There's a self loop over state $q_4$ for inputs $1$ and $b$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/25864