0

I am interested to see how a for loop / while loop would be implemented as an automaton. I am having difficulty imagining how that would work. Say the while-loop did this:

var i = 0
while (i < 10) i = i + 1

Not sure what happens if that were implemented as an automaton (what the states and transitions would be, and where the operation i = i + 1 would occur in the automaton). Wondering if one could show the main states and transitions of this if it were an automaton.

Improve this question
2
  • 1
    What kind of automaton? If you are talking about FSMs, then a WHILE loop is pretty much the defining thing that it cannot do. – Jörg W Mittag Jun 22 '18 at 13:09
  • I am talking about any possible automaton, most likely not an FSM. I am interested in things like register automata, timed automata, i/o automata, graph automata, nfas, etc. Looking for any sort of automaton that can model the while loop without creating a new state for each iteration. – Lance Pollard Jun 22 '18 at 14:22
3

It looks like this:

   i++  i++  i++  i++  i++  i++  i++  i++  i++  i++
(0)->(1)->(2)->(3)->(4)->(5)->(6)->(7)->(8)->(9)->(10)

Each time you change i you're changing state. Loops require state to be different on each iteration so they won't look like loops when graphed as automata that show variable state. This isn't the typical usage of automata since there actually isn't an external input controlling the transitions. It's just the program repeatedly executing state mutating code.

Improve this answer
3
  • Wondering if there is any way not to have it be a separate state per iteration, maybe a different kind of automaton. Was hoping there is like an "active" state and an "idle" state, and that (say in a register automaton / automata with memory) the i would just be accumulating in memory, while the state stayed the same, or toggled back and forth or something. – Lance Pollard Jun 22 '18 at 12:45
  • 1
    Are you looking for something like a timed automaton? – candied_orange Jun 22 '18 at 12:54
  • Not sure if you're suggesting that timed automata can handle while loops without creating states for each iteration. That would be cool! – Lance Pollard Jun 22 '18 at 19:29

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.