EvalVis / EvalVis/TuringMachine
Add finite-state machine
- Dominant language
- TypeScript
- Stars
- 0
- Forks
- 0
- PR merge metrics
- No merged PRs in 30d
Description
**Describe the feature**
Finite-state machine is a less powerful subset of a Turing machine, which has a simpler configuration and can recognize regular languages.
Finite-state machine compared to Turing machine can only:
1. Move right - cannot move left or stay in the same cell.
2. Is read-only.
Therefore, the transition table is simpler and consists of:
current state, current value -> next state.
Special rule:
Finite-automata stops when reaching last non-blank symbol on the right.
It has final states as classical Turing machine but reaching the final state does not cause the finite-state machine to halt. Only reaching the end of input causes the machine to halt.
Task: implement finite-state machine.
**Describe alternatives you've considered (optional)**
Although user could use classical Turing machine the Finite-state machine has simplified setup for simpler problems and therefore it is good to have it.
**Additional context**
Example of what finite-state machine can recognize:
Does input of multiple letters a and b and with ab?
With this instruction table the finite-state machine prints the answer:
q0,a,q1
q0,b,q0
q1,a,q1
q1,b,q2
q2,a,q1
q2,b,q0
You can check it with input aabaab
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.