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

Example

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

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.

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;

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

Sprint-4

Sprint-3

Sprint-2

Sprint-1

Motivation

Credit: TikZ & PGF Manual

• https://anorien.csc.warwick.ac.uk/mirrors/CTAN/graphics/pgf/base/doc/pgfmanual.pdf
• https://plantuml.com/

References

• https://dart.dev/
• https://flutter.dev/
• https://pub.dev/packages/petitparser
• https://pub.dev/packages/flutter_bloc
• https://pub.dev/packages/test

Code Generator

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