Project to create a domain-specific language to describe a Turing machine for visual rendering.
Application URL - https://groupsvkg.github.io
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;
- 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 ✔️
- 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.
- 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.
- 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. ✔️
- 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. ✔️
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>
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 |
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 |
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 |
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 |
Name |
Description |
play |
command to start Turing Machine simulation |
show |
command to show subset of transitions |
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
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
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 |
Credit: TikZ & PGF Manual
- Flutter
- flutter packages pub run build_runner watch
- flutter packages pub run build_runner build --delete-conflicting-outputs