Lets construct a DFA over{a,b} That accepts only the string "aabb" in it. My problem with this video is that the tutor has moved arrow from state D to B why didn't he set a self loop on D .Im really helpless .

Move forward to minute 11

  • 1
    $\begingroup$ You should improve the title. It is too broad. Please take some time to improve it. $\endgroup$ – fade2black Oct 23 '17 at 23:24
  • $\begingroup$ The question should be self contained, could you transcribe relevant part? $\endgroup$ – Evil Oct 25 '17 at 20:02
  • $\begingroup$ @fade2black may I start a conversation with you if that doesn't bother you ?I'm new to this website sorry for posting answers instead of comments $\endgroup$ – Kolyx akos Oct 30 '17 at 17:18

Your purpose is to detect a substring $aabb$. When the FA is in state $D$ it already has read $aab$ (pay attention that in order to get to $D$ from the start state the FA must read $aab$ or $a\dots aab$). While in state $D$ there are two possible inputs: $a$ or $b$. If it reads $a$ it enters the state $B$ because it already has $a$ (it remains to read $abb$). On $b$ it enters the accept state. If on $a$ it stays on $D$ then it would accept a wrong string, for example, $aabab$ which does not contain $aabb$ as a substring. In other words, on $a$ you should send it back to the state $B$ as if FA switches from state $A$ into state $B$.

  • $\begingroup$ @user93 Your proposed FA is not correct. Please see the related video. $\endgroup$ – fade2black Oct 24 '17 at 5:59
  • $\begingroup$ the question description says that it needs to only accept string "aabb" not string with sub-string "aabb" $\endgroup$ – user93 Oct 24 '17 at 6:07
  • $\begingroup$ @user93 it says "...That accepts only the string "aabb" in it.". You can also watch the video. $\endgroup$ – fade2black Oct 24 '17 at 6:13
  • $\begingroup$ I didn't see that coming I have added a new DFA $\endgroup$ – user93 Oct 24 '17 at 6:20
  • $\begingroup$ @user93 it is still wrong. The back-transition should go to the second state from the left. Also label all states like in the video. You can draw the DFA exactly like in the video. $\endgroup$ – fade2black Oct 24 '17 at 6:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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