1
$\begingroup$

I am trying to draw a DFA that accepts the following language:

$L=\{a^{2i+5j} : i , j \geq 0\}$

I started out by drawing an NFA, which I can then convert to a DFA but I am not sure if my NFA is correct.

NFA

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Your language contains all words except $a,aaa$. $\endgroup$
    – Yuval Filmus
    May 18, 2019 at 21:15
  • 1
    $\begingroup$ Add a transition from q5 to q0. The state q6 can be removed $\endgroup$
    – John L.
    May 19, 2019 at 2:34

3 Answers 3

Reset to default
0
$\begingroup$

I'm not sure if this NFA is correct since both outgoing options from q0 are 'a', which means that you would not know to which node to go to. Wikipedia also defines an NFA as an FA when "each of its transitions is uniquely determined by its source state and input symbol", and less relevant "reading an input symbol is required for each state transition". The transistions of node q0 are not uniquely defined in this case.

Furthermore, even if two outgoing 'a's are allowed, once you have gone to q2, no multiples of 2 are possible anymore in your NFA.

That said, I do not know if you can really draw a good NFA since your definition of L allows for quite some correct multiples of a. You could start by making a list of all possible options: $$[0,2,4,6,8,10] \;for\; (i \geq 0 , j= 0)\\ [0,5,10,15,20] \;for\; (i=0,j\geq 0) \\ [7,9,11,13,15] \;for\; (i\geq1, j=1)\\$$ From which you can quickly deduce that after 4, every even and uneven numbers are possible. Which gives the following NFA:

NFA of definition L

But I'm actually guessing you just wish to parse every multiple of 5 or 2, with tokens of either "aa" or "aaaaa". In which case you need the following NFA:

NFA to parse multiples of 2 and 5

This works, since a parser would restart after 5 'a' s since no other state can be reached. Furthermore, it can parse "aaaa", since it remembers the last accepting state, which would be q2, and starts over with the 'leftover' bit of "aa". Which it can parse again.

Normally you would also have to take into account the fact that a parser is greedy, however, this parser is rather simple, as such this is not a problem. However, in long strings of 'a' you would only get tokens of "aaaaa" until the end. At that point it might parse tokens of 2 in the case of leftover strings of "aa" or "aaaa".

SIDENOTE: Do not start your NFA with an accepting state of q0, since that means you could have infinitely many empty tokens.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Forgive if I am being too direct. There have been multiple elementary errors in the answer. $\endgroup$
    – John L.
    May 19, 2019 at 2:40
  • $\begingroup$ What are infinitely many empty tokens? Where did you get those from? $\endgroup$
    – Evil
    May 19, 2019 at 3:54
  • $\begingroup$ @Apass.Jack can you please explain the errors? $\endgroup$
    – Judith
    May 19, 2019 at 10:34
  • $\begingroup$ @Evil What I meant is that when you implement this DFA, trying to parse only "a". You would go to an error state after q1, accept your last accepting state q0, which is empty (""). After which it will again try to parse leftover bit, namely "a", and continue like this forever. However, this is only true for implemented parsers by a computer programm, and I suppose I did assume this would be the case. $\endgroup$
    – Judith
    May 19, 2019 at 10:39
2
$\begingroup$

All natural numbers are expressible in the form $2x+5y$, except for $1,3$. You can check this directly, of use the solutino of the Frobenius problem for two denominations. Therefore another way to write your language (assuming the alphabet is $\{a\}$) is $$ \overline{\{a,a^3\}}. $$ You can construct a DFA for this language using 5 states, that count up to 4 and then saturate.

If you want to implement the constraint $2x+5y$ directly as an NFA (which is more economical for larger values of $2,5$), then you construct the following NFA:

  • States: $q_0,a_1,b_1,b_2,b_3,b_4$.
  • Initial state: $q_0$.
  • Final states: $\{q_0\}$.
  • Transition function: $$ \begin{array}{c|cccccc} q & q_0 & a_1 & b_1 & b_2 & b_3 & b_4 \\\hline \delta(q,a) & a_1,b_1 & q_0 & b_2 & b_3 & b_4 & q_0 \end{array} $$

In words, there is a 2-cycle and a 5-cycle sharing a vertex $q_0$, which is also the initial state and the unique final state.

Improve this answer
$\endgroup$
-1
$\begingroup$

Yes, the NFA looks correct to me.

Improve this answer
$\endgroup$
3
  • $\begingroup$ $ q0 -> q1 -> q0 -> q2 -> q3 -> q4 -> q5 -> q6 $ , do you see anything wrong with this run? q6 is an accepting state. $\endgroup$
    – SiluPanda
    May 19, 2019 at 7:19
  • $\begingroup$ Care to explain the reason of the downvote? $\endgroup$
    – SiluPanda
    May 19, 2019 at 7:20
  • $\begingroup$ you're right, that does recognise $a^7$. $\endgroup$
    – rici
    May 19, 2019 at 7:34

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.