-1
$\begingroup$

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$
$T$: $H$ X $I$ X $S$ \rightarrow $M$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$

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.