EvalVis / EvalVis/TuringMachine

Add finite-state machine

Aperta
#2 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub
enhancement good first issue
Lingua principale
TypeScript
Stelle
0
Fork
0
Metriche di merge delle PR
Nessuna PR unita negli ultimi 30g

Descrizione

**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

Guida per i contributori

Nessuna guida per i contributori indicizzata per questo repository

Direzione di ricerca

Inizia leggendo l’implementazione esistente della macchina di Turing e il modo in cui accetta tabelle di transizione e input. Usa la tabella q0/q1/q2 fornita e l’input aabaab come esempio di comportamento. Il lavoro è completo quando il progetto supporta una macchina a stati finiti con transizioni esclusivamente verso destra e di sola lettura, e si arresta alla fine dell’input.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Valutazione

Stack tecnologico
typescript
Ambito
compilers
Tipo di issue
Funzionalità
Difficoltà
5/5
Tempo stimato
Più di una settimana
Stato di attività
Ferma
Chiarezza
Abbastanza chiara
Idoneità per principianti
35/100

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.