* 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
