This question is an exact duplicate of:

I have two languages:

  1. $\{a^n b^m \mid n, m > 0, n - m = 0 \pmod 3\}$

  2. $\{a^n b^m \mid n, m > 0, n + m = 0 \pmod 3\}$

and I'm having trouble drawing automata for them.

For the first language, I know that the first valid pairs are ab | aabb | aaaab | aaabbb, but I'm having trouble drawing that and putting it into a general automaton.

I know the for the second language, S ← abb|aab|aaabbb are the first valid pairs, but I again don't know how to put it into a general automaton.


enter image description here


marked as duplicate by Martin Sleziak, zhoraster, drhab, martini, Joel Reyes Noche Oct 8 '15 at 12:34

This question was marked as an exact duplicate of an existing question.

  • $\begingroup$ You asked this same question two days ago and got an answer then. If you didn't understand the answer, post comments there. $\endgroup$ – amd Oct 8 '15 at 4:57

In question $1$, you can manipulate the equation a bit and get $n = m \pmod 3$. This isn't vital or very profound, but it may help your thinking.

For both of these, you can take different paths depending on the number of $a$'s you get. The first part that deals with $a$'s will always be the same. You should have three states $X$, $Y$, $YZ$ with the following property: if you're in state $X$, you just read a number of $a$'s congruent to $0 \pmod 3$, if you're in state $Y$, you just read a number of $a$'s congruent to $1 \pmod 3$, if you're in state $Z$, you just read a number of $a$'s congruent to $2 \pmod 3$.

I would make a closed loop of $3$ states for this part.

(Q: Which state should you start in?)

Then, what do you do when you're in one of $X, Y, Z$ and you read a $b$? You move to the next stage, where you find the number of $b$'s $\pmod 3$ and accept only if it matches the value for $a$.

Another closed loop would be appropriate here, since you might need to read an unbounded number of $b$'s. You'll need to rig things up so that you accept only the right thing.

(Hint: You can do this with $12$ states or $6$.)

  • $\begingroup$ Ahhh I'm still stumped, have no idea what to do, thanks for your answer though, did clear some things up $\endgroup$ – user270494 Oct 8 '15 at 3:48
  • $\begingroup$ Where are you stumped -- any chance I can help further? (You don't need to accept my answer until it satisfies you.) $\endgroup$ – Eli Rose Oct 8 '15 at 4:22
  • $\begingroup$ What do you mean by closed loop of 3 states? I have X -a-> Y -aa-> YZ $\endgroup$ – user270494 Oct 8 '15 at 4:40
  • $\begingroup$ By a closed loop of 3 states I mean that as long as you keep reading $a$'s, you should be in one of states X, Y or Z. Not sure what that notation means -- what is YZ? $\endgroup$ – Eli Rose Oct 8 '15 at 4:47
  • $\begingroup$ so do you mean like X -ab-> Y -aabb-> Z? But I thought NFA's could only read one character at a time $\endgroup$ – user270494 Oct 8 '15 at 5:00

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