1

Im trying to construct finite automata in the form of diagrams accepting certain languages.

One is in all parts the alphabet is $\{a, b\}$. Construct FA $\{w \mid w \text{ has neither $aa$ nor $bb$ as a subword}\}$

I understand that for any word with $aa$ or $bb$ in it, it should not be able to get in to finite state. How ever, after drawing many diagrams with a trial and error approach I'm not really getting anywhere.

How can I construct a FA diagram to prove this rule?

Thanks, Ciaran

J.-E. Pin
  • 40,163
user202051
  • 11

2 Answers2

1

You only need three states for an incomplete deterministic automaton. Just add a sink state and the corresponding transitions (dashed transitions in the diagram below) to get a complete DFA for your language.enter image description here

J.-E. Pin
  • 40,163
0
  1. Start in state $q_i$
  2. If you are an in state $q_i$ and read $a$ then move to $q_a$
  3. If you are an in state $q_i$ and read $b$ then move to $q_b$
  4. If you are an in state $q_a$ and read $a$ then move to $q_{aa}$
  5. If you are an in state $q_a$ and read $b$ then move to $q_b$
  6. If you are an in state $q_b$ and read $a$ then move to $q_a$
  7. If you are an in state $q_b$ and read $b$ then move to $q_{bb}$
  8. accept in $q_a, q_b$ and reject in $q_{aa}, q_{bb}$.
azarel
  • 13,120
  • Can't there only be one accepting state? – user202051 Oct 20 '14 at 00:12
  • @CiaranAshton You can make $q_{aa}=q_{bb}=q_f$ if you only want an acceptance state. – azarel Oct 20 '14 at 00:28
  • Okay I see. Thank you very much. – user202051 Oct 20 '14 at 00:32
  • The other one im having trouble with is {w|w has an even number of a's and odd number of b's} How could this work? – user202051 Oct 20 '14 at 00:33
  • @Ciaran: Have states $q_{00},q_{01},q_{10}$, and $q_{11}$, and design the transitions so that you’re in state $q_{ij}$ when the number of $a$s that you’ve read is congruent to $i$ mod $2$ and the number of $b$s that you’ve read is congruent to $j$ mod $2$. You should have no trouble figuring out which of these four states should be the initial state and which one(s) should accept. – Brian M. Scott Oct 20 '14 at 02:22
  • @Ciaran Normally, an automaton is allowed to have more than one accepting state. – MJD Oct 21 '14 at 15:18