finite_automata.html

   1 <html>
   2 <title>Finite Automata</title>
   3 <noscript>
   4         <b>Your browser does not support JavaScript or JavaScript is disabled.</b>
   5 </noscript>
   6 <script>
   7 var PI = 3.141592654;
   8 var TWO_PI = PI * 2;
   9
  10 var BLUE   = "#00f";
  11 var GREEN  = "#0f0";
  12 var RED    = "#f00";
  13 var YELLOW = "#ff0";
  14
  15 var stage = new Array();        /* status of stage - all details stored here    */
  16 var store = new Array();        /* status of input                                                              */
  17
  18 var bit_x = null;               /* location of current bit in grid                              */
  19 var bit_y = null;               /* see above - 0,0 is top left of grid                  */
  20
  21 var stage_rows = 8;                     /* number of rows on stage                                              */
  22 var stage_cols = 9;                     /* number of columns on stage                                   */
  23 var store_bit_count = 10;       /* number of bits stored in machine                             */
  24
  25 var input_count = 10;           /* number of input bits                                                 */
  26
  27 var grid_status = 1;            /* turn grid lines on and off                                   */
  28 var grid_size = 50;                     /* size in pixels of grid lines - both X and Y  */
  29 var canvas;                                     /* object id of canvas tag                                              */
  30 var canvas_input;                       /* object id of input tag                                               */
  31
  32 var ctx;                                        /* context of canvas                                                    */
  33 var input;                                      /* context of input canvas                                              */
  34
  35 /* each square on grid has an associated block of data tied to it */
  36 function grid(type, bit, dir, col){
  37         this.type = type;       /* type of machine part                         */
  38         this.bit  = bit;        /* data in this block - if any          */
  39         this.dir  = dir;        /* direction this item is turned        */
  40         this.col  = col;        /* color of machine part (if any)       */
  41 }
  42
  43 /* this is used to display all bits on all active items */
  44 function test_types(){
  45         var i = 0, j = 0, k = 1, l = 2, col = 1;
  46         for(i = 0; i < stage_rows; i++) {
  47                 for(j = 0; j < stage_rows; j++){
  48                         if(k == 6) { k = 1; }
  49                         switch(k){
  50                                 case 1: stage[i][j].type = "branch"; break;
  51                                 case 2: stage[i][j].type = "bus"; break;
  52                                 case 3: stage[i][j].type = "input"; break;
  53                                 case 4: stage[i][j].type = "output"; break;
  54                                 case 5:
  55                                         stage[i][j].type = "bitadd";
  56                                         if(col == 5) { col = 1; }
  57                                         switch(col){
  58                                                 case 1: stage[i][j].col = RED;    break;
  59                                                 case 2: stage[i][j].col = GREEN;  break;
  60                                                 case 3: stage[i][j].col = YELLOW; break;
  61                                                 case 4: stage[i][j].col = BLUE;   break;
  62                                         };
  63                                         col++;
  64                                         break;
  65                         };
  66                         k++;
  67                         if(l == 5) { l = 1; }
  68                         switch(l){
  69                                 case 1: stage[i][j].bit = RED;    break;
  70                                 case 2: stage[i][j].bit = GREEN;  break;
  71                                 case 3: stage[i][j].bit = YELLOW; break;
  72                                 case 4: stage[i][j].bit = BLUE;   break;
  73                         };
  74                         l++;
  75                 }
  76         }
  77 }
  78
  79 /* create all output data structures and draw inital values on screen */
  80 function init_stage(){
  81         var x; var y;
  82
  83         /* create blank grid data structure */
  84         for(x = 0; x < stage_cols; x++) {
  85                 stage[x] = new Array();
  86                 for(y = 0; y < stage_rows; y++) {
  87                         stage[x][y] = new grid('', '', '', '');
  88                 }
  89         }
  90         stage[5][0].type = "input";
  91         stage[5][1].type = "branch";
  92
  93         stage[5][2].type = "bus";
  94         stage[5][2].dir = 1;
  95
  96         stage[6][2].type = "bus";
  97         stage[6][2].dir = 3;
  98         stage[6][1].type = "bus";
  99         stage[6][1].dir = 2;
 100
 101         stage[5][6].type = "branch";
 102         stage[5][7].type = "branch";
 103         stage[5][8].type = "output";
 104
 105         stage[0][1].type = "bus";
 106         stage[0][1].dir = 1;
 107
 108         stage[5][3].type = "output";
 109         //stage[5][3].col = "red";
 110
 111         stage[5][4].type = "bus";
 112         stage[5][4].dir = 4;
 113
 114         stage[6][4].type = "bus";
 115         stage[6][4].dir = 3;
 116
 117         stage[6][3].type = "bus";
 118         stage[6][3].dir = 2;
 119
 120         stage[0][2].type = "bitadd";
 121         stage[0][2].col = GREEN;
 122         stage[0][3].type = "bus";
 123         stage[0][3].dir = 3;
 124         stage[0][4].type = "bus";
 125         stage[0][4].dir = 4;
 126
 127         stage[5][1].type = "bus";
 128         stage[5][1].dir = 1;
 129
 130         //test_types();
 131 }
 132
 133 /* moves automata to next position */
 134 function next_move(){
 135         // if input is empty - get next bit
 136         if(!bit_x){
 137                 move_getbit();
 138         } else {
 139                 // determine what type of machine part we are on
 140                 switch(stage[bit_x][bit_y].type){
 141                         case "bitadd":
 142                                 move_bitadd();
 143                                 break;
 144                         case "branch":
 145                                 move_branch();
 146                                 break;
 147                         case "bus":
 148                                 move_bus();
 149                                 break;
 150                         case "input":
 151                                 move_input();
 152                                 break;
 153                         case "output":
 154                                 move_output();
 155                                 break;
 156                         default:
 157                                 alert("Unknown entity.");
 158                 };
 159         }
 160 }
 161
 162 function move_getbit(){
 163         stage[5][0].bit = store.shift();
 164         draw_tape();
 165         draw_tile(5,0);
 166         bit_x = 5; bit_y = 0;
 167 }
 168
 169 function move_bitadd(){
 170         // TODO: temove this switch statement
 171         store.push(stage[bit_x][bit_y].col);
 172         stage[bit_x][bit_y+1].bit = stage[bit_x][bit_y].bit;
 173         stage[bit_x][bit_y].bit = "";
 174         draw_tile(bit_x,bit_y);
 175         draw_tile(bit_x,bit_y+1);
 176         draw_tape();
 177         bit_y++;
 178 }
 179
 180 // determine which direction to move and move there
 181 function move_branch(){
 182         if(stage[bit_x][bit_y].bit == BLUE){
 183                 stage[bit_x+1][bit_y].bit = stage[bit_x][bit_y].bit;
 184                 stage[bit_x][bit_y].bit = "";
 185                 draw_tile(bit_x,bit_y);
 186                 draw_tile(bit_x+1,bit_y);
 187                 bit_x++;
 188         } else if (stage[bit_x][bit_y].bit == RED){
 189                 stage[bit_x-1][bit_y].bit = stage[bit_x][bit_y].bit;
 190                 stage[bit_x][bit_y].bit = "";
 191                 draw_tile(bit_x,bit_y);
 192                 draw_tile(bit_x-1,bit_y);
 193                 bit_x--;
 194         } else {
 195                 stage[bit_x][bit_y+1].bit = stage[bit_x][bit_y].bit;
 196                 stage[bit_x][bit_y].bit = "";
 197                 draw_tile(bit_x,bit_y);
 198                 draw_tile(bit_x,bit_y+1);
 199                 bit_y++;
 200         }
 201 }
 202
 203 function move_bus(){
 204         var x = 0, y = 0;
 205         // 1= DOWN; 2= LEFT; 3 = UP; 4 = LEFT
 206         switch(stage[bit_x][bit_y].dir){
 207                 case 1:
 208                         y++;
 209                         break;
 210                 case 2:
 211                         x--;
 212                         break;
 213                 case 3:
 214                         y--;
 215                         break;
 216                 case 4:
 217                         x++;
 218                         break;
 219                 default:
 220                         alert("Unknown bus direction.");
 221         };
 222         stage[bit_x+x][bit_y+y].bit = stage[bit_x][bit_y].bit;
 223         stage[bit_x][bit_y].bit = "";
 224         draw_tile(bit_x,bit_y);
 225         bit_y += y; bit_x += x;
 226         draw_tile(bit_x,bit_y);
 227 }
 228
 229 function move_input(){
 230         var i, j;
 231         // look for entity next to input.
 232         // walk around clockwise until one is found
 233         if(stage[bit_x][bit_y+1].type){
 234                 stage[bit_x][bit_y+1].bit = stage[bit_x][bit_y].bit;
 235                 stage[bit_x][bit_y].bit = "";
 236                 draw_tile(bit_x,bit_y);
 237                 draw_tile(bit_x,bit_y+1);
 238                 bit_y++;
 239         } else { alert("Cannot continue: No connection to input."); }
 240 }
 241
 242 // if we are on an output, remove bit and move to an input
 243 function move_output(){
 244         stage[bit_x][bit_y].bit = "";
 245         draw_tile(bit_x,bit_y);
 246         bit_x = null; bit_y = null;
 247 }
 248
 249 /* set initial values for input */
 250 function init_input(){
 251         store.push(RED);
 252         store.push(BLUE);
 253         store.push(YELLOW);
 254         store.push(GREEN);      /* add to end           */
 255         //store.unshift("red"); /* add to front         */
 256         //store.pop();          /* remove from end      */
 257         //store.shift();        /* remove from front    */
 258 }
 259
 260 /* draw faint gridlines on stage - used as a guide for the user */
 261 function draw_grid(){
 262         var x, y; /* current x and y position */
 263         var offset = 10; /* x and y maximum offset (far bottom or side of the window) */
 264         ctx.strokeStyle = "#ccc";
 265         ctx.lineWidth = 1;
 266         /* draw vertical lines */
 267         for(x = grid_size, y = 0, offset = window.innerWidth; x < window.innerWidth; x = x + grid_size){
 268                 ctx.beginPath();
 269                 ctx.moveTo(x,y);
 270                 ctx.lineTo(x,y+offset);
 271                 ctx.stroke();
 272                 stage_cols++;
 273         }
 274         /* draw horizontal lines */
 275         for(x = 0, y = grid_size, offset = window.innerWidth; y < window.innerWidth; y = y + grid_size){
 276                 ctx.beginPath();
 277                 ctx.moveTo(x,y);
 278                 ctx.lineTo(x+offset,y);
 279                 ctx.stroke();
 280                 stage_rows++;
 281         }
 282 }
 283
 284 /*
 285 move through each grid in stage and draw contents.
 286 this function can be used to refresh the screen at any time.
 287 */
 288 function draw_stage(){
 289         var x; var y;
 290         /* loop through all grids on stage, drawing contents */
 291         for(x=0; x < stage_cols; x++){
 292                 for(y = 0; y < stage_rows; y++){
 293                         draw_tile(x,y);
 294                 }
 295         }
 296 }
 297
 298 /* delete item from stage */
 299 function stage_delete(){
 300
 301 }
 302
 303 /* add current item to stage at clicked location */
 304 function stage_add(){
 305
 306 }
 307
 308 /* select this item as next item to be placed */
 309 function stage_select(){
 310
 311
 312 }
 313
 314 function init_form(){
 315         var x; var y;
 316         /* initalize canvas element for use */
 317         canvas = document.getElementById("stage");
 318         ctx = canvas.getContext("2d");
 319
 320         canvas_input = document.getElementById("input");
 321         input = canvas_input.getContext("2d");
 322
 323         /* get width and height of window and set stage (canvas) with it. */
 324         canvas.height = window.innerHeight-125;
 325         canvas.width = window.innerWidth - 45;
 326         if(grid_status){draw_grid(); }
 327         init_stage();
 328         draw_stage();
 329         init_input();
 330         draw_tape();
 331 }
 332
 333 /* returns coordinates of canvas in pixels */
 334 function cnvs_get_coordinates(e){
 335         var x_offset = canvas.offsetLeft;
 336         var y_offset = canvas.offsetTop;
 337         if(canvas == 'undefined'){ alert("Canvas parameter is undefined"); }
 338         x_offset = e.clientX - x_offset;
 339         y_offset = e.clientY - y_offset;
 340         document.getElementById("xycoordinates").innerHTML="Coordinates: (" + x_offset + "," + y_offset + ")";
 341         return [x_offset,y_offset];
 342 }
 343
 344 /* move through tape and draw bits */
 345 function draw_tape(){
 346         var i = 0; var x = 50;
 347         input.fillStyle = "#f00";
 348         input.clearRect(0,0,579,100);
 349         while(i < store.length){
 350                         input.beginPath();
 351                         input.fillStyle = store[i];
 352                         input.arc(x,25,20,0,TWO_PI,0);
 353                         input.fill();
 354
 355                         input.strokeStyle = "#000";
 356                         input.lineWidth = 2;
 357                         input.beginPath();
 358                         input.arc(x,25,20,0,TWO_PI,0);
 359                         input.stroke();
 360                 x += 50;
 361                 i++;
 362         }
 363         /* icons for each type */
 364         input.save();
 365         input.translate(0, grid_size);
 366         draw_trash();
 367         input.restore();
 368 }
 369
 370 /* (re)draws any map tile on grid */
 371 function draw_tile(x,y){
 372         ctx.save();
 373         ctx.translate(grid_size * x, grid_size * y);
 374         switch (stage[x][y].type){
 375                 case "bitadd":
 376                         draw_bitadd(stage[x][y].col);
 377                         break;
 378                 case "branch":
 379                         draw_branch();
 380                         break;
 381                 case "bus":
 382                         draw_bus(stage[x][y].dir);
 383                         break;
 384                 case "input":
 385                         draw_input();
 386                         break;
 387                 case "output":
 388                         draw_output();
 389                         break;
 390                 default: clear_square();
 391         };
 392
 393         if(stage[x][y].bit){ draw_bit(stage[x][y].bit); }
 394         ctx.restore();
 395 }
 396
 397 function draw_trash(){
 398         input.strokeStyle = "#000";
 399         input.lineCap = "round";
 400         input.lineWidth = 12;
 401         input.beginPath();
 402         input.moveTo(10,10);
 403         input.lineTo(grid_size-10,grid_size-10);
 404         input.stroke();
 405         input.beginPath();
 406         input.moveTo(10, grid_size-10);
 407         input.lineTo(grid_size-10, 10);
 408         input.stroke();
 409
 410         input.strokeStyle = "#f00";
 411         input.lineWidth = 8;
 412         input.beginPath();
 413         input.moveTo(10,10);
 414         input.lineTo(grid_size-10,grid_size-10);
 415         input.stroke();
 416         input.beginPath();
 417         input.moveTo(10, grid_size-10);
 418         input.lineTo(grid_size-10, 10);
 419         input.stroke();
 420 }
 421
 422 /* draws small bit of correct color on grid */
 423 function draw_bit(color){
 424         ctx.fillStyle = "#f00";
 425         ctx.beginPath();
 426         ctx.fillStyle = color;
 427         ctx.arc(25,25,10,0,TWO_PI,0);
 428         ctx.fill();
 429
 430         ctx.strokeStyle = "#000";
 431         ctx.lineWidth = 2;
 432         ctx.beginPath();
 433         ctx.arc(25,25,10,0,TWO_PI,0);
 434         ctx.stroke();
 435 }
 436
 437 /* draw gray square with black outline */
 438 function draw_input(){
 439         ctx.lineWidth = 1;
 440         ctx.strokeStyle = "#000";
 441         ctx.strokeRect(0,0,grid_size,grid_size);
 442         ctx.fillStyle = "#aaa";
 443         ctx.fillRect(0,0,grid_size,grid_size);
 444 }
 445
 446 function drawSpirograph(ctx,R,r,O){
 447   var x1 = R-O;
 448   var y1 = 0;
 449   var i  = 1;
 450   ctx.beginPath();
 451   ctx.moveTo(x1,y1);
 452   do {
 453     if (i>20000) break;
 454     var x2 = (R+r)*Math.cos(i*Math.PI/72) - (r+O)*Math.cos(((R+r)/r)*(i*Math.PI/72))
 455     var y2 = (R+r)*Math.sin(i*Math.PI/72) - (r+O)*Math.sin(((R+r)/r)*(i*Math.PI/72))
 456     ctx.lineTo(x2,y2);
 457     x1 = x2;
 458     y1 = y2;
 459     i++;
 460   } while (x2 != R-O && y2 != 0 );
 461   ctx.stroke();
 462 }
 463
 464 function draw_output(){
 465         ctx.fillStyle = "#fff";
 466         ctx.fillRect(2,2,grid_size-2,grid_size-2); /* clear grid */
 467
 468         ctx.translate(grid_size/2,grid_size/2);
 469         ctx.strokeStyle = "#d80";
 470         ctx.lineWidth = 2;
 471         drawSpirograph(ctx,9,2,7);
 472         ctx.translate(-(grid_size/2),-(grid_size/2));
 473 }
 474
 475 /* a bus moves bits from one location to another */
 476 function draw_bus(dir){
 477         var i = 0;
 478
 479         ctx.fillStyle = "#fff";
 480         ctx.fillRect(2,2,grid_size-2,grid_size-2); /* clear grid */
 481
 482         ctx.lineWidth = 2;
 483         ctx.fillStyle = "#aaa";
 484         ctx.strokeStyle = "#000";
 485
 486         switch(dir){
 487                 case 2:
 488                         ctx.translate(grid_size,0);
 489                         ctx.rotate(PI/2);
 490                         break;
 491                 case 3:
 492                         ctx.translate(grid_size,grid_size);
 493                         ctx.rotate(PI);
 494                         break;
 495                 case 4:
 496                         ctx.translate(0,grid_size);
 497                         ctx.rotate(-PI/2);
 498                         break;
 499         };
 500
 501         while(i < 2){
 502                 if(i == 1) { ctx.save(); ctx.translate(0, grid_size/2); }
 503                 ctx.beginPath();
 504                 ctx.moveTo(0,0);
 505                 ctx.lineTo(grid_size/2,grid_size/2);
 506                 ctx.lineTo(grid_size,0);
 507                 ctx.lineTo(grid_size/2,grid_size/4);
 508                 ctx.closePath();
 509                 ctx.fill();
 510
 511                 ctx.beginPath();
 512                 ctx.moveTo(0,0);
 513                 ctx.lineTo(grid_size/2,grid_size/2);
 514                 ctx.lineTo(grid_size,0);
 515                 ctx.lineTo(grid_size/2,grid_size/4);
 516                 ctx.closePath();
 517                 ctx.stroke();
 518                 if(i == 1) { ctx.restore(); }
 519                 i++;
 520         }
 521 }
 522
 523 /* tiles branch movement of each bit */
 524 function draw_branch(){
 525         /* left */
 526         ctx.lineWidth = 1;
 527         ctx.fillStyle = "#f00";
 528         ctx.beginPath();
 529         ctx.moveTo(0,0);
 530         ctx.lineTo(grid_size/2,grid_size/2);
 531         ctx.lineTo(0,grid_size);
 532         ctx.closePath();
 533         ctx.fill();
 534
 535          /* top */
 536         ctx.fillStyle = "#000";
 537         ctx.beginPath();
 538         ctx.moveTo(0,0)
 539         ctx.lineTo(grid_size/2,grid_size/2);
 540         ctx.lineTo(grid_size,0);
 541         ctx.closePath();
 542         ctx.fill();
 543
 544
 545          /* right */
 546         ctx.fillStyle = "#00f";
 547         ctx.beginPath();
 548         ctx.moveTo(grid_size,0);
 549         ctx.lineTo(grid_size/2,grid_size/2);
 550         ctx.lineTo(grid_size,grid_size);
 551         ctx.closePath();
 552         ctx.fill();
 553
 554          /* bottom */
 555         ctx.fillStyle = "#aaa";
 556         ctx.beginPath();
 557         ctx.moveTo(0,grid_size)
 558         ctx.lineTo(grid_size/2,grid_size/2);
 559         ctx.lineTo(grid_size,grid_size);
 560         ctx.closePath();
 561         ctx.fill();
 562 }
 563
 564 function draw_bitadd(color){
 565         var i = 0;
 566         while(i < 2){
 567                 if(i==1){
 568                         ctx.strokeStyle = color;
 569                         ctx.lineWidth = 10;
 570                 } else {
 571                         ctx.strokeStyle = "#000";
 572                         ctx.lineWidth = 15;
 573                 }
 574                 ctx.beginPath();
 575                 ctx.moveTo(grid_size/2,0);
 576                 ctx.lineTo(grid_size/2,grid_size);
 577                 ctx.closePath();
 578                 ctx.stroke();
 579
 580                 ctx.beginPath();
 581                 ctx.moveTo(0, grid_size/2);
 582                 ctx.lineTo(grid_size,grid_size/2);
 583                 ctx.closePath();
 584                 ctx.stroke();
 585                 i++;
 586         }
 587         ctx.strokeStyle = "#000";
 588         ctx.lineWidth = 1;
 589         ctx.beginPath();
 590         ctx.moveTo(0, 0);
 591         ctx.lineTo(0,grid_size);
 592         ctx.lineTo(grid_size,grid_size);
 593         ctx.lineTo(grid_size,0);
 594         ctx.lineTo(0,0);
 595         ctx.closePath();
 596         ctx.stroke();
 597 }
 598
 599 /* clear this square by setting area to white */
 600 function clear_square(){
 601         ctx.fillStyle = "#fff";
 602         ctx.fillRect(1,1,grid_size-2,grid_size-2);
 603 }
 604
 605 /* canvas has been clicked find out which grid and make correct change to square if needed. */
 606 function cnvs_clicked(e){}
 607
 608 </script>
 609
 610 <style type="text/css">
 611
 612 </style>
 613
 614 <body onLoad="init_form();">
 615
 616 <div id="topsection">
 617
 618 <center>
 619 <button onClick='reset();'><img src="http://opentextbook.info/icons/32x32/resultset_first.png" title="Restart" alt="Restart"></button>
 620 &nbsp;&nbsp;
 621 <button onClick='step_back();'><img src="http://opentextbook.info/icons/32x32/resultset_previous.png" title="Step Back" alt="Step Back"></button>
 622 &nbsp;&nbsp;
 623 <button onClick='next_move();'><img src="http://opentextbook.info/icons/32x32/resultset_next.png" title="Next Step" alt="Next Step"></button>
 624 &nbsp;&nbsp;
 625 <button onClick='run();'><img src="http://opentextbook.info/icons/32x32/resultset_last.png" title="Run" alt="Run"></button>
 626 &nbsp;&nbsp;
 627
 628 <!--
 629 <button onClick='halt();'><img src="http://opentextbook.info/icons/32x32/cancel.png" title="Halt Execution" alt="Halt Execution"></button>
 630 &nbsp;&nbsp;
 631
 632 <button disabled><img src="http://opentextbook.info/icons/32x32/disk.png" title="Save Code" alt="Save Code"></button>
 633 &nbsp;&nbsp;
 634 <button onClick='display_docs();'><img src="http://opentextbook.info/icons/32x32/book_open.png" title="Open Documentation" alt="Open Documentation"></button>
 635 -->
 636 </center>
 637
 638 </div>
 639
 640 <div id="xycoordinates">Coordinates:</div>
 641 <canvas id="input" width="579" height="100"></canvas>
 642 <canvas id="stage" width="579" height="770" onmousemove="cnvs_get_coordinates(event)" onclick="cnvs_clicked(event);">
 643 Your browser does not support HTML5 Canvas.
 644 </canvas>
 645
 646 </body>
 647 </html>