0
$\begingroup$

I'm trying to draw two automata for these two languages: enter image description here

For the first one, I know that the minimum is n = 1, m = 1, but I'm having troubles drawing a NFA for it.

The second one the minimum is n = 2, m = 1, but I still don't know how to start the NFA.

I have this for q2:

enter image description here

$\endgroup$
  • $\begingroup$ it might help you to realize that n-m = 0 mod 3 if and only if n mod 3 - m mod 3 = 0. So you could store n mod 3 as you loop through the a's, and then resolve the b's differently based on what you get for n mod 3. It works similarly for the second one. $\endgroup$ – nivekgnay Oct 5 '15 at 4:10
  • $\begingroup$ You might want to ask your computer science questions at Computer Science Stack Exchange. $\endgroup$ – Joel Reyes Noche Oct 8 '15 at 3:43
0
$\begingroup$

Look at small numbers first. For the second language, the first valid $(n,m)$ pairs are $(1,2)$, $(2,1)$, $(3,3)$, and all others are of the form $(3k+n,3l+m)$, where $(n,m)$ is one of the starting pairs.

Hence the language can be described by $S \leftarrow abb|aab|aaabbb|aaaS|Sbbb$. It should be straightforward to draw an automata from this description.

enter image description here

$\endgroup$
  • $\begingroup$ sorry I'm just having trouble deciding how many states I should have? $\endgroup$ – user270494 Oct 5 '15 at 17:23
  • $\begingroup$ I think a minimal DFA would be 12 states. Just draw the automata. You can use as many states as you like. $\endgroup$ – copper.hat Oct 5 '15 at 17:42
  • $\begingroup$ Ah, I haven't been able to construct one yet - I am stumped $\endgroup$ – user270494 Oct 8 '15 at 2:49
  • $\begingroup$ I may have been a little quick with my comment. I was about to add a DFA and realised I made a big mistake. $\endgroup$ – copper.hat Oct 8 '15 at 3:13
  • $\begingroup$ what do you mean you made a big mistake? $\endgroup$ – user270494 Oct 8 '15 at 3:22

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.