0
$\begingroup$

I did following exercise and i want to clarify that did i made something wrong. And cannot figure out how to solve the c th question.

Questions

answers that i got

Answers

$\endgroup$
4
  • $\begingroup$ Your answer to (b) is alright, but your answer to (a) does not contain a final state... Which states did you mean to be final? $\endgroup$
    – AsafHaas
    Apr 21 '17 at 10:41
  • $\begingroup$ @AsafHaas aah i forgot to add that q1 must be the final state. i forgot to draw that. :) now, how i figure out C $\endgroup$
    – Siba Boba
    Apr 21 '17 at 10:44
  • $\begingroup$ I afraid that your answer for (a) is incorrect... Check for example that the word $w = 111$ is accepted by your automata, but $n_1(w) = 0 \pmod{3} $ $\endgroup$
    – AsafHaas
    Apr 21 '17 at 10:47
  • $\begingroup$ Cross-posted: math.stackexchange.com/q/2244821/14578, cs.stackexchange.com/q/74295/755. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$
    – D.W.
    Apr 21 '17 at 16:04
0
$\begingroup$

I afraid that your answer for (a) is incorrect... Check for example that the word $w = 111$ is accepted by your automata, but $n_1(w) = 0 \pmod{3}$.

Label the states in your answer to (a) as: $$q_0: n_1(w) = 0 \pmod{3}$$ $$q_1: n_1(w) = 1 \pmod{3}$$ $$q_2: n_1(w) = 2 \pmod{3}$$ and try to figure out for each arrow where it should go, what will be the states of $w$.

Here is a NFA for (c):

NFA for (c)

$\endgroup$
1
  • $\begingroup$ Thanks for clarifying :). Yeah i made a mistake in a th one. i'll try it again :) $\endgroup$
    – Siba Boba
    Apr 21 '17 at 10:59
0
$\begingroup$

In case you want to check the DFA that recognizes the set $\{100w001|w\in\{0, 1\}^*\}$

enter image description here

$\endgroup$
2
  • $\begingroup$ I guess the transitions for $q_7$ go into itself? $\endgroup$
    – matrixx
    May 1 '17 at 12:35
  • $\begingroup$ Yes it does. Its a trapping state. Sorry I forgot to draw. $\endgroup$ May 1 '17 at 14:28

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.