1
$\begingroup$

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:
DFA graph

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

Improve this question
$\endgroup$
5
  • $\begingroup$ This question is a follow up to two previous questions by the same user, and it should reference them. The OP does not seem to understand that his way of finding answers is not adequate, and he should learn general techniques for building FA, DFA, regular expressions and the like. Asking repeatedly for the same specific problem is wasting his time and ours. He should read a textbook on regular laguages and finite automata, or ask for pointers on the web if he cannot access a textbook. Is that the case? He should fill his SE profile so that we can know if he has a problem. $\endgroup$
    – babou
    May 19, 2014 at 13:51
  • $\begingroup$ If giving straight answers to the questions is a quite problematic task for you, do not answer. I'm not forcing you to waste your own precious time. Besides, right now you are 'wasting your time' on useless writing your negative review. When I have time, I also help people to find solutions to the problems they can not decide, by giving the straight answers to the questions. And this is normal. $\endgroup$
    – Happy Torturer
    May 19, 2014 at 21:19
  • $\begingroup$ There is a saying: give a fish to a person and he will eat today, but if you teach him to fish, he will eat everyday. You should learn to fish rather than keep asking everyday for a new fish. I told you there are systematic techniques to build these things related to finite state automata. That is what you should learn. Trap states are not a tool that you can use or not use. Their presence depends only on a property of the language you are defining, and there is nothing you can do about it. They will necessarily be one (at least) if needed, and none if not needed. $\endgroup$
    – babou
    May 19, 2014 at 22:01
  • $\begingroup$ "They will necessarily be one (at least) if needed". No, the Trap state is not necessary for building an FA, even at least one. Assume that the language chain has to start from '01' and contain an odd number of '1', having VT = {0,1,2}. The shortest chain here will be '01', so there're minimum 3 states: q0,q1,q2, where q2 will be the end state. There're 2 ways: to use a trap state (between q0 and q1) or to use an extra state q3 (going after the q2) instead. There will be the only way to enter/exit into/from q3 state - terminal '1', while q3 has it's own cycle (0,2). $\endgroup$
    – Happy Torturer
    May 20, 2014 at 11:00
  • $\begingroup$ "You should learn to fish rather than keep asking everyday for a new fish." - You are talking like a real fisherman! $\endgroup$
    – Happy Torturer
    May 20, 2014 at 11:15

1 Answer 1

Reset to default
1
$\begingroup$

enter image description here

$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$.

Improve this answer
$\endgroup$
12
  • $\begingroup$ But how to move from $q_2$ to $q_3$ for 1,b terminals and what does an overline over $'a'$ terminal mean? Or it means "not a" like in probability theory? I've never seen terminals with overlines in any of my theory examples. $\endgroup$
    – Happy Torturer
    May 18, 2014 at 11:00
  • $\begingroup$ When we reach $q_2$, it means we have $1a$ as the prefix of string and previous symbol encountered is $a$, for example $1aa, 1abbba, 1a111ba$ etc. If we encounter another $a$(consecutive), we reach $q_3$. We move to $q_4$ from $q_2$ if we scan symbol other than $a$ i.e $1$ or $b$. $\endgroup$
    – donkey
    May 18, 2014 at 11:10
  • $\begingroup$ Let's suppose we've just read $'1'$ or $'b'$ terminal while being in the state $q_2$. We moved to $q_4$, right? But then, while being in $q_4$, we get another $'1'$ or $'b'$ terminal. How will the DFA get out of the state $q_4$? I suppose that $q_4$ needs a not-$a$-cycle. $\endgroup$
    – Happy Torturer
    May 18, 2014 at 11:25
  • $\begingroup$ When in $q_4$, all inputs except $a$, do not change state of DFA. Only input $a$ will cause DFA to move out of $q_4$. $\endgroup$
    – donkey
    May 18, 2014 at 11:32
  • 1
    $\begingroup$ Yes. Trap state is parser's way of saying "No matter what input you give me now, I am not going to accept this string" i.e the string fails to satisfy it's needs even before the whole string is parsed. $\endgroup$
    – donkey
    May 18, 2014 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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