<p>I think you are describing a pushdown automaton: <a href="https://en.wikipedia.org/wiki/Pushdown_automaton" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Pushdown_automaton</a></p>

CC BY-SA 4.0
2019-07-21T12:00:23.587Z
2019-07-21T14:22:04.797Z
2019-07-21T14:22:04.797Z
mpc
<p>The formal definition of a finite state machine is as follows:<br>
A FSM is a quintuple:<br>
(<span class="math-container">$I$</span>, <span class="math-container">$S$</span>, <span class="math-container">$S$</span><sub>0</sub>, <span class="math-container">$T$</span>, <span class="math-container">$F$</span>)<br>
<span class="math-container">$I$</span> - finite, non-empty input set<br>
<span class="math-container">$S$</span> - finite, non-empty state set<br>
<span class="math-container">$S$</span><sub>0</sub> - initial state<br>
<span class="math-container">$T$</span> - transition function<br>
<span class="math-container">$T$</span>: <span class="math-container">$S$</span> X <span class="math-container">$I$</span> \rightarrow <span class="math-container">$S$</span><br>
<span class="math-container">$F$</span> - finite, non-empty set of final states<br></p>

<p>Now I am attempting to modify the definition for a stacked based FSM. A stack based FSM keeps track of previous states entered. I need critique on the newly modified definition.</p>

<p>A stacked-based FSM can be defined by the following:<br>
It is a septuple (<span class="math-container">$I$</span>, <span class="math-container">$S$</span>, <span class="math-container">$S$</span><sub>0</sub>, <span class="math-container">$H$</span>, <span class="math-container">$M$</span>, <span class="math-container">$T$</span>, <span class="math-container">$F$</span>)<br>
<span class="math-container">$I$</span> - finite, non-empty input set<br>
<span class="math-container">$S$</span> - finite, non-empty state set<br>
<span class="math-container">$S$</span><sub>0</sub> - initial state<br>
<span class="math-container">$H$</span> - finite state set<br>
<span class="math-container">$M$</span> - modify stack function<br>
<span class="math-container">$T$</span> - transition function<br>
<span class="math-container">$F$</span> - finite, non-empty set of final states<br></p>

<p><span class="math-container">$M$</span>: <span class="math-container">$H$</span> X <span class="math-container">$S$</span> X <span class="math-container">$I$</span> \rightarrow <span class="math-container">$H$</span><br/>
<span class="math-container">$T$</span>: <span class="math-container">$H$</span> X <span class="math-container">$I$</span> X <span class="math-container">$S$</span> \rightarrow <span class="math-container">$M$</span><br/></p>

<p>Reasoning:<br>
<span class="math-container">$M$</span> is the function that updates the stack set, <span class="math-container">$H$</span>, by using the stack, the current state and the input to determine if the stack can be modified.<br>
<span class="math-container">$T$</span> is the function that cause state transition, therefore, to transition between states it requires the stack, the input and the current state and will output a state that will be used in the <span class="math-container">$M$</span> function.<br></p>

<p>References:<br>
<a href="https://en.wikipedia.org/wiki/Finite-state_machine" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Finite-state_machine</a></p>

<automata-theory>
What is the formal definition of a stacked based finite state machine?
heyblackduck
# What is the formal definition of a stacked based finite state machine?

(Asked by: username_0 on 2019-07-19)

The formal definition of a finite state machine is as follows:  
A FSM is a quintuple:  
($I$, $S$, $S$0, $T$, $F$)  
$I$ - finite, non-empty input set  
$S$ - finite, non-empty state set  
$S$0 - initial state  
$T$ - transition function  
$T$: $S$ X $I$ \rightarrow $S$  
$F$ - finite, non-empty set of final states

Now I am attempting to modify the definition for a stacked based FSM. A stack based FSM keeps track of previous states entered. I need critique on the newly modified definition.

A stacked-based FSM can be defined by the following:  
It is a septuple ($I$, $S$, $S$0, $H$, $M$, $T$, $F$)  
$I$ - finite, non-empty input set  
$S$ - finite, non-empty state set  
$S$0 - initial state  
$H$ - finite state set  
$M$ - modify stack function  
$T$ - transition function  
$F$ - finite, non-empty set of final states

$M$: $H$ X $S$ X $I$ \rightarrow $H$

Reasoning:  
$M$ is the function that updates the stack set, $H$, by using the stack, the current state and the input to determine if the stack can be modified.  
$T$ is the function that cause state transition, therefore, to transition between states it requires the stack, the input and the current state and will output a state that will be used in the $M$ function.

References:  
<https://en.wikipedia.org/wiki/Finite-state_machine>

**Tags:** automata-theory

---

## 1 answers

### Answer by username_1 on 2019-07-21. Score: 3 | Accepted answer

I think you are describing a pushdown automaton: <https://en.wikipedia.org/wiki/Pushdown_automaton>


---

