Add finite-state machine

Open
#2 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
5/5
Estimated time
Over a week
Newbie friendliness
35/100
Issue type
Feature
Clarity
Mostly clear
Activity status
Stale
Tech stack
typescript
Domain
compilers

Research direction

Start by reading the existing Turing machine implementation and how it accepts transition tables and input. Use the supplied q0/q1/q2 table and input aabaab as the behavioral example. Done means the project supports a finite-state machine with right-only, read-only transitions and halts at the end of input.

Written by the indexing model from the issue text.

Description

enhancement good first issue

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

Dominant language
TypeScript
Stars
0
Forks
0
No merged PRs in 30d

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from EvalVis/TuringMachine

All issues in EvalVis/TuringMachine

Similar issues

More TypeScript issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.