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;
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
- https://anorien.csc.warwick.ac.uk/mirrors/CTAN/graphics/pgf/base/doc/pgfmanual.pdf
- https://plantuml.com/
- https://dart.dev/
- https://flutter.dev/
- https://pub.dev/packages/petitparser
- https://pub.dev/packages/flutter_bloc
- https://pub.dev/packages/test
- Flutter
- flutter packages pub run build_runner watch
- flutter packages pub run build_runner build --delete-conflicting-outputs