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