Skip to content

Latest commit

 

History

History
436 lines (372 loc) · 19.6 KB

README.md

File metadata and controls

436 lines (372 loc) · 19.6 KB

Turing Machine Simulator

Project to create a domain-specific language to describe a Turing machine for visual rendering.

Demo

Application URL - https://groupsvkg.github.io

Turing Machine Simulator

Example

image

tm M {
  tape : --|0000--;

  state[ x=250, y=390, initial ] : q1;
  state[ below of=q1, rejecting ] : qr;
  state[ right of=q1 ] : q2;
  state[ below of=q2, accepting ] : qa;
  state[ right of=q2, distance=300 ] : q3;
  state[ above right of=q2 ] : q5;
  state[ below of=q3 ]: q4;

  q1 -[ bend right ]-> qr : e, e, R;
  q1 -[ bend left ]-> qr : x, x, R;
  q1 --> q2 : 0, e, R;

  q2 --> qa : e, e, R;
  q2 --> q2 : x, x, R;
  q2 --> q3: 0, x, R;

  q3 --> q3: x, x, R;
  q3 --> q5: e, e, L;
  q3 -[ bend right ]-> q4 : 0, 0, R;

  q4 -[ loop right ]-> q4 : x, x, R;
  q4 -[ bend right ]-> q3 : 0, x, R;
  q4 -[ bend left ]-> qr : e, e, R;

  q5 --> q5 : 0, 0, L;
  q5 -[ loop right ]-> q5: x, x, L;
  q5 --> q2 : e, e, R;
}

play color=#blue duration=4;

Project Plan

image

Sprints

Sprint-5

  • Added "play" command to trigger animation ✔️
  • Implemented new logic for transition arrow rendering. ✔️
  • Implemented color name in addition to hex color code. ✔️
  • Added deviation attribute for transition arrow to vary bezier control point. ✔️
  • Able to show computations. ✔️
  • Able to list computations. ✔️
  • Added documentation link ✔️
  • Added video link ✔️
  • Fixed computation rendering issue ✔️
  • Fixed animation restart issue ✔️
  • Implemented Accept/Reject indication to occur after animation completes ✔️
  • Implemented rendering of tape with no input initialized i.e. --|-- ✔️
  • Implemented "duration" parameter to control animation duration ✔️
  • Fixed incorrect transition rendering count ✔️
  • Added code snippet buttons in toolbar ✔️
  • Implemented timeout message if number of computation exceeds "max" value (default max=100) ✔️
  • Fixed transition arrow issue for the case of states having different radius ✔️

Sprint-4

  • Implemented state rendering and logic for state attributes. ✔️
  • Implemented rendering for initial state indicator. ✔️
  • Implemented accepting and rejecting state. ✔️
  • Implemented transition rendering and logic for state attributes. ✔️
  • Implemented self loop transitions. ✔️
  • Implemented label rendering on transition arrows. ✔️
  • Implemented empty cells for tape rendering. ✔️
  • Highlighted current head cell on tape. ✔️
  • Implemented error indication of parse failure. ✔️
  • Implemented delay of 700 milliseconds for rendering. ✔️
  • TODO
    • Implement loop distance attribute so that arrow bending can be controlled by user.
    • Implement animation for computations.
    • Add vedio demo for application functionality.
    • Create survey for user feedback.
    • Allow color names in addition to hex code.
    • Update testcases.
    • Update Grammar in this document.

Sprint-3

  • Updated grammar to fix visual attributes associated with state, transition, and Turing Machine. ✔️
  • Written testcases for the updated grammar. ✔️
  • Able to render Tape cell, State. ✔️
  • Refined grammar.
    • Replaced comma with space for attribute seperation. ✔️
  • Finalized code representation of Cell, Head, Tape, States, State, Transitions, Transition, and Turing Machine. ✔️
  • Implemented Composite pattern to represent Turing Machine. ✔️
  • Able to render complete Tape i.e. Tape with Cells and Head. ✔️
  • User can control various attributes of Tape i.e. position, border and text color. ✔️
  • TODO
    • Update testcases.
    • Update Grammar in this document.

Sprint-2

  • Designed language grammar. ✔️
  • Implemented language grammar and parser. ✔️
  • Written unit test cases for language grammar and parser. ✔️
  • Integrated parser component in HomePage. ✔️
  • Able to extract data from user input. ✔️
  • Deployed new web build on Github. ✔️

Sprint-1

  • Created flutter project on Github. ✔️
  • Implemented user interface for HomePage. ✔️
  • Implemented business logic component(BLoC) for HomePage. ✔️
  • Tested UI update on user text input. ✔️
  • Deployed web build to Github. ✔️

Grammar

Operator Description
* zero or more
+ one or more
? optional
<turing-machine> ::= <tm-token> <tm-name> <tm-attribute-list>? <left-curly-brace> <statements> <right-curly-brace>

<!-- Tm -->
<tm-token> ::= <ignore-character> "tm" <ignore-character>
<tm-name> = <ignore-character> <word>+ <ignore-character>
<tm-attribute-list> ::= <attributes>*

<!-- Attributes -->
<attributes> ::= <left-square-bracket> <pair> ( <comma> <pair> )* <right-square-bracket>
<pair> ::= <key> ( <assignment> <value> )?
<key> ::= <letter>+ ( <whitespace>+ <letter>+ )*
<value> ::= <word>+

<!-- Statements -->
<statements> ::= <tape>? <states>? <transitions>?

<!-- Tape -->
<tape> ::= (<tape-token> <tape-attributes> <colon>)? <tape-data> <semicolon>
<tape-token> ::= <ignore-character> "tape" <ignore-character>
<tape-attributes> ::= <attributes>?
<tape-data> ::= <tape-start> <word>* <head> <word>* <tape-end>
<tape-start> ::= "--"
<head> ::= "|"
<tape-end> ::= "--"

<!-- States -->
<states> ::= <state>*
<state> ::= <state-token> <state-attributes> <colon> <state-name> <semicolon>
<state-token> ::= <ignore-character> "state" <ignore-character>
<state-attributes> ::= <attributes>?
<state-name> ::= <word>+

<!-- Transitions -->
<transitions> ::= <transition>*
<transition> ::= <source> (<transition-operation> | <hyphen> <transition-attributes> <arrow>) <destination> (<colon> <label>)
<source> ::= <word>+
transition-operation ::= "->"
<transition-attributes> ::= <attributes>?
<destination> ::= <word>+
<label> ::= <label-first> <comma> <label-middle> <comma> <label-last>
<label-first> ::= <word>
<label-middle> ::= <word>
<label-last> ::= <head-left> | <head-right>

<head-left> ::= <ignore-character> "L" <ignore-character>
<head-right> ::= <ignore-character> "R" <ignore-character>

<word> ::= <letter> | <digit>
<letter> ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | 
             "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | 
             "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | 
             "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | 
             "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | 
             "y" | "z"
 <digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
 <ignore-character> ::= <tab> | <newline> | <whitespace>
 <tab> ::= "\t"
 <newline> ::= <unix-newline> | <windows-newline>
 <whitespace> ::= " "
 <unix-newline> ::= "\n"
 <windows-newline> ::= "\r\n"
 <comma> ::= <ignore-character> "," <ignore-character>
 <colon> ::= <ignore-character> ":" <ignore-character>
 <semicolon> ::= <ignore-character> ";" <ignore-character>
 <hyphen> ::= "-"
 <assignment> ::= <ignore-character> "=" <ignore-character>
 <arrow> ::= "->"
 <left-curly-brace> ::= <ignore-character> "{" <ignore-character>
 <right-curly-brace> ::= <ignore-character> "}" <ignore-character>
 <left-square-bracket> ::= <ignore-character> "[" <ignore-character>
 <right-square-bracket> ::= <ignore-character> "]" <ignore-character>

Example

Below is the Turing Machine M for language L consisting of all strings of 0s whose length is a power of 2.

image

tm M {
  tape : --|0000--;

  state[ x=250, y=390, initial ] : q1;
  state[ below of=q1, rejecting ] : qr;
  state[ right of=q1 ] : q2;
  state[ below of=q2, accepting ] : qa;
  state[ right of=q2, distance=300 ] : q3;
  state[ above right of=q2 ] : q5;
  state[ below of=q3 ]: q4;

  q1 -[ bend right ]-> qr : e, e, R;
  q1 -[ bend left ]-> qr : x, x, R;
  q1 --> q2 : 0, e, R;

  q2 --> qa : e, e, R;
  q2 --> q2 : x, x, R;
  q2 --> q3: 0, x, R;

  q3 --> q3: x, x, R;
  q3 --> q5: e, e, L;
  q3 -[ bend right ]-> q4 : 0, 0, R;

  q4 -[ loop right ]-> q4 : x, x, R;
  q4 -[ bend right ]-> q3 : 0, x, R;
  q4 -[ bend left ]-> qr : e, e, R;

  q5 --> q5 : 0, 0, L;
  q5 -[ loop right ]-> q5: x, x, L;
  q5 --> q2 : e, e, R;
}

play color=#blue;

image

Turing Machine Attributes

Key Value Type Description
fill color background color
distance number distance between states

Tape Attributes

Key Value Type Description
x number x coordinate of tape center
y number y coordinate of tape center
cell height number cell height
cell width number cell width
cell stroke width number cell stroke width
cell stroke color color cell stroke color
cell fill color color cell fill color
symbol color color cell label color
symbol font size number cell label font size
head height number head vertical length including tip
head tip height number head tip height
head tip width number head tip width
head stroke width number head stroke width
head stroke color color head stroke color

State Attributes

Key Value Type Description
x number x coordinate of state center
y number y coordinate of state center
r number radius of state circle
stroke width number stroke width
stroke color color stroke color
fill color color fill color of state circle
symbol color color state label color
symbol margin number label left and right margin
symbol font size number label font size
initial - indicates that state is initial
initial above - initial arrow is above the state vertically
initial below - initial arrow is below the state vertically
initial left - initial arrow is left the state vertically
initial right - initial arrow is right the state vertically
accepting - indicates accepting state
rejecting - indicates rejecting state
intermediate - indicates intermediate state
above of string indicates relative position of state
below of string indicates relative position of state
left of string indicates relative position of state
right of string indicates relative position of state
above right of string indicates relative position of state
above left of string indicates relative position of state
below right of string indicates relative position of state
below left of string indicates relative position of state
distance number indicates relative distance with other state

Transition Attributes

Key Value Type Description
stroke width number stroke width
stroke color color stroke color
loop above - self loop position
loop above left - self loop position
loop above right - self loop position
loop below - self loop position
loop below left - self loop position
loop below right - self loop position
loop left - self loop position
loop right - self loop position
loop distance number self loop height
bend left - bend arrow left
bend right - bend arrow right
label first color color arrow label first character color
label middle color color arrow label middle character color
label last color color arrow label last character color
label font size number label font size
above - label above arrow
below - label below arrow
deviation number transition arrow end points angle

Commands

Name Description
play command to start Turing Machine simulation
show command to show subset of transitions

Play Attributes

Key Value Type Description
color color simulation color indication
duration number simulation duration in seconds
from number transition start number
to number transition end number
max number maximum transition to display

Example: play color=#red duration=3

Show Attributes

Key Value Type Description
color color simulation color indication
duration number simulation duration
from number transition start number
to number transition end number

Example: show color=#green duration=4 from=2 to=4

Colors

Name Hexcode
#white #FFFFFF
#silver #C0C0C0
#gray #808080
#black #000000
#red #FF0000
#maroon #800000
#yellow #FFFF00
#olive #808000
#lime #00FF00
#green #008000
#aqua #00FFFF
#teal #008080
#blue #0000FF
#navy #000080
#fuchsia #FF00FF
#purple #800080

User Interface

Sprint-5

image image image image

Sprint-4

image image image image image image image image

Sprint-3

image image image image image image image

Sprint-2

image image

Sprint-1

image image

Motivation

image

Credit: TikZ & PGF Manual

References

Code Generator

  • Flutter
    • flutter packages pub run build_runner watch
    • flutter packages pub run build_runner build --delete-conflicting-outputs