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 stage_rows = 8;             /* number of rows on stage                              */
  19 var stage_cols = 9;             /* number of columns on stage                           */
  20 var store_bit_count = 10;       /* number of bits stored in machine                     */
  21
  22 var input_count = 10;           /* number of input bits                                 */
  23
  24 var grid_status = 1;            /* turn grid lines on and off                           */
  25 var grid_size = 50;             /* size in pixels of grid lines - both X and Y          */
  26 var canvas;                     /* object id of canvas tag                              */
  27 var canvas_input;               /* object id of input tag                               */
  28
  29 var ctx;                        /* context of canvas                                    */
  30 var input;                      /* context of input canvas                              */
  31
  32 /* each square on grid has an associated block of data tied to it */
  33 function grid(type, bit, dir, col){
  34         this.type = type;       /* type of machine part                         */
  35         this.bit  = bit;        /* data in this block - if any          */
  36         this.dir  = dir;        /* direction this item is turned        */
  37         this.col  = col;        /* color of machine part (if any)       */
  38 }
  39
  40 /* this is used to display all bits on all active items */
  41 function test_types(){
  42         var i = 0, j = 0, k = 1, l = 2, col = 1;
  43         for(i = 0; i < stage_rows; i++) {
  44                 for(j = 0; j < stage_rows; j++){
  45                         if(k == 6) { k = 1; }
  46                         switch(k){
  47                                 case 1: stage[i][j].type = "branch"; break;
  48                                 case 2: stage[i][j].type = "bus"; break;
  49                                 case 3: stage[i][j].type = "input"; break;
  50                                 case 4: stage[i][j].type = "output"; break;
  51                                 case 5:
  52                                         stage[i][j].type = "bitadd";
  53                                         if(col == 5) { col = 1; }
  54                                         switch(col){
  55                                                 case 1: stage[i][j].col = RED;    break;
  56                                                 case 2: stage[i][j].col = GREEN;  break;
  57                                                 case 3: stage[i][j].col = YELLOW; break;
  58                                                 case 4: stage[i][j].col = BLUE;   break;
  59                                         };
  60                                         col++;
  61                                         break;
  62                         };
  63                         k++;
  64                         if(l == 5) { l = 1; }
  65                         switch(l){
  66                                 case 1: stage[i][j].bit = RED;    break;
  67                                 case 2: stage[i][j].bit = GREEN;  break;
  68                                 case 3: stage[i][j].bit = YELLOW; break;
  69                                 case 4: stage[i][j].bit = BLUE;   break;
  70                         };
  71                         l++;
  72                 }
  73         }
  74 }
  75
  76 /* create all output data structures and draw inital values on screen */
  77 function init_stage(){
  78         var x; var y;
  79
  80         /* create blank grid data structure */
  81         for(x = 0; x < stage_cols; x++) {
  82                 stage[x] = new Array();
  83                 for(y = 0; y < stage_rows; y++) {
  84                         stage[x][y] = new grid('', '', '', '');
  85                 }
  86         }
  87         stage[5][0].type = "input";
  88         stage[5][0].bit = "red";
  89         stage[5][1].type = "branch";
  90         stage[5][2].type = "bus";
  91         stage[5][6].type = "branch";
  92         stage[5][7].type = "branch";
  93         stage[5][8].type = "output";
  94
  95         stage[0][1].type = "bus";
  96         stage[0][1].dir = 1;
  97
  98         stage[0][2].type = "bus";
  99         stage[0][2].dir = 2;
 100         stage[0][3].type = "bus";
 101         stage[0][3].dir = 3;
 102         stage[0][4].type = "bus";
 103         stage[0][4].dir = 4;
 104
 105         //test_types();
 106 }
 107
 108 /* moves automata to next position */
 109 function next_move(){
 110
 111         // determine what type of machine part we are on
 112
 113         // if we are on a bus move to next grid
 114
 115         // if we are on an input, make next bit dissappear from tape
 116         // place bit on input
 117
 118         // if we are on a branch, determine which direction to move
 119         // and move there
 120
 121         // if we are on an output, remove bit and move to an input
 122 }
 123
 124 /* set initial values for input */
 125 function init_input(){
 126         store.push(RED);
 127         store.push(BLUE);
 128         store.push(YELLOW);
 129         store.push(GREEN);      /* add to end           */
 130         //store.unshift("red"); /* add to front         */
 131         //store.pop();          /* remove from end      */
 132         //store.shift();        /* remove from front    */
 133 }
 134
 135 /* draw faint gridlines on stage - used as a guide for the user */
 136 function draw_grid(){
 137         var x, y; /* current x and y position */
 138         var offset = 10; /* x and y maximum offset (far bottom or side of the window) */
 139         ctx.strokeStyle = "#ccc";
 140         ctx.lineWidth = 1;
 141         /* draw vertical lines */
 142         for(x = grid_size, y = 0, offset = window.innerWidth; x < window.innerWidth; x = x + grid_size)
 143         {
 144                 ctx.beginPath();
 145                 ctx.moveTo(x,y);
 146                 ctx.lineTo(x,y+offset);
 147                 ctx.stroke();
 148                 stage_cols++;
 149         }
 150         /* draw horizontal lines */
 151         for(x = 0, y = grid_size, offset = window.innerWidth; y < window.innerWidth; y = y + grid_size)
 152         {
 153                 ctx.beginPath();
 154                 ctx.moveTo(x,y);
 155                 ctx.lineTo(x+offset,y);
 156                 ctx.stroke();
 157                 stage_rows++;
 158         }
 159 }
 160
 161 /*
 162 move through each grid in stage and draw contents.
 163 this function can be used to refresh the screen at any time.
 164 */
 165 function draw_stage(){
 166         var x; var y;
 167         /* loop through all grids on stage, drawing contents */
 168         for(x=0; x < stage_cols; x++) {
 169                 for(y = 0; y < stage_rows; y++) {
 170                         draw_tile(x,y);
 171                 }
 172         }
 173 }
 174
 175 function init_form(){
 176         var x; var y;
 177         /* initalize canvas element for use */
 178         canvas = document.getElementById("stage");
 179         ctx = canvas.getContext("2d");
 180
 181         canvas_input = document.getElementById("input");
 182         input = canvas_input.getContext("2d");
 183
 184         /* get width and height of window and set stage (canvas) with it. */
 185         canvas.height = window.innerHeight-125;
 186         canvas.width = window.innerWidth - 45;
 187         if(grid_status) {draw_grid(); }
 188         init_stage();
 189         draw_stage();
 190         init_input();
 191         draw_tape();
 192 }
 193
 194 /* returns coordinates of canvas in pixels */
 195 function cnvs_get_coordinates(e){
 196         var x_offset = canvas.offsetLeft;
 197         var y_offset = canvas.offsetTop;
 198         if(canvas == 'undefined') { alert("Canvas parameter is undefined"); }
 199         x_offset = e.clientX - x_offset;
 200         y_offset = e.clientY - y_offset;
 201         document.getElementById("xycoordinates").innerHTML="Coordinates: (" + x_offset + "," + y_offset + ")";
 202         return [x_offset,y_offset];
 203 }
 204
 205 /* move through tape and draw bits */
 206 function draw_tape(){
 207         var i = 0; var x = 50;
 208         input.fillStyle = "#f00";
 209         while(i < input_count){
 210                 if(store[i]) {
 211                         input.beginPath();
 212                         input.fillStyle = store[i];
 213                         input.arc(x,25,20,0,TWO_PI,0);
 214                         input.fill();
 215
 216                         input.strokeStyle = "#000";
 217                         input.lineWidth = 2;
 218                         input.beginPath();
 219                         input.arc(x,25,20,0,TWO_PI,0);
 220                         input.stroke();
 221                 }
 222                 x += 50;
 223                 i++;
 224         }
 225 }
 226
 227 /* (re)draws any map tile on grid */
 228 function draw_tile(x,y){
 229         ctx.save();
 230         ctx.translate(grid_size * x, grid_size * y);
 231         switch (stage[x][y].type){
 232                 case "bitadd":
 233                         draw_bitadd(stage[x][y].col);
 234                         break;
 235                 case "branch":
 236                         draw_branch();
 237                         break;
 238                 case "bus":
 239                         draw_bus(stage[x][y].dir);
 240                         break;
 241                 case "input":
 242                         draw_input();
 243                         break;
 244                 case "output":
 245                         draw_input();
 246                         break;
 247                 default: clear_square();
 248         };
 249
 250         if(stage[x][y].bit){ draw_bit(stage[x][y].bit); }
 251         ctx.restore();
 252 }
 253
 254 /* draws small bit of correct color on grid */
 255 function draw_bit(color){
 256         ctx.fillStyle = "#f00";
 257         ctx.beginPath();
 258         ctx.fillStyle = color;
 259         ctx.arc(25,25,10,0,TWO_PI,0);
 260         ctx.fill();
 261
 262         ctx.strokeStyle = "#000";
 263         ctx.lineWidth = 2;
 264         ctx.beginPath();
 265         ctx.arc(25,25,10,0,TWO_PI,0);
 266         ctx.stroke();
 267 }
 268
 269 /* draw gray square with black outline */
 270 function draw_input(){
 271         ctx.lineWidth = 1;
 272         ctx.strokeStyle = "#000";
 273         ctx.strokeRect(0,0,grid_size,grid_size);
 274         ctx.fillStyle = "#aaa";
 275         ctx.fillRect(0,0,grid_size,grid_size);
 276 }
 277
 278 /* a bus moves bits from one location to another */
 279 function draw_bus(dir){
 280         var i = 0;
 281         ctx.lineWidth = 2;
 282         ctx.fillStyle = "#aaa";
 283         ctx.strokeStyle = "#000";
 284
 285         switch(dir){
 286                 case 2:
 287                         ctx.translate(grid_size,0);
 288                         ctx.rotate(PI/2);
 289                         break;
 290                 case 3:
 291                         ctx.translate(grid_size,grid_size);
 292                         ctx.rotate(PI);
 293                         break;
 294                 case 4:
 295                         ctx.translate(0,grid_size);
 296                         ctx.rotate(-PI/2);
 297                         break;
 298         };
 299
 300         while(i < 2){
 301                 if(i == 1) { ctx.save(); ctx.translate(0, grid_size/2); }
 302                 ctx.beginPath();
 303                 ctx.moveTo(0,0);
 304                 ctx.lineTo(grid_size/2,grid_size/2);
 305                 ctx.lineTo(grid_size,0);
 306                 ctx.lineTo(grid_size/2,grid_size/4);
 307                 ctx.closePath();
 308                 ctx.fill();
 309
 310                 ctx.beginPath();
 311                 ctx.moveTo(0,0);
 312                 ctx.lineTo(grid_size/2,grid_size/2);
 313                 ctx.lineTo(grid_size,0);
 314                 ctx.lineTo(grid_size/2,grid_size/4);
 315                 ctx.closePath();
 316                 ctx.stroke();
 317                 if(i == 1) { ctx.restore(); }
 318                 i++;
 319         }
 320 }
 321
 322 /* tiles branch movement of each bit */
 323 function draw_branch(){
 324         /* left */
 325         ctx.lineWidth = 1;
 326         ctx.fillStyle = "#f00";
 327         ctx.beginPath();
 328         ctx.moveTo(0,0);
 329         ctx.lineTo(grid_size/2,grid_size/2);
 330         ctx.lineTo(0,grid_size);
 331         ctx.closePath();
 332         ctx.fill();
 333
 334          /* top */
 335         ctx.fillStyle = "#000";
 336         ctx.beginPath();
 337         ctx.moveTo(0,0)
 338         ctx.lineTo(grid_size/2,grid_size/2);
 339         ctx.lineTo(grid_size,0);
 340         ctx.closePath();
 341         ctx.fill();
 342
 343
 344          /* right */
 345         ctx.fillStyle = "#00f";
 346         ctx.beginPath();
 347         ctx.moveTo(grid_size,0);
 348         ctx.lineTo(grid_size/2,grid_size/2);
 349         ctx.lineTo(grid_size,grid_size);
 350         ctx.closePath();
 351         ctx.fill();
 352
 353          /* bottom */
 354         ctx.fillStyle = "#aaa";
 355         ctx.beginPath();
 356         ctx.moveTo(0,grid_size)
 357         ctx.lineTo(grid_size/2,grid_size/2);
 358         ctx.lineTo(grid_size,grid_size);
 359         ctx.closePath();
 360         ctx.fill();
 361 }
 362
 363 function draw_bitadd(color){
 364         var i = 0;
 365         while(i < 2){
 366                 if(i==1){
 367                         ctx.strokeStyle = color;
 368                         ctx.lineWidth = 10;
 369                 } else {
 370                         ctx.strokeStyle = "#000";
 371                         ctx.lineWidth = 15;
 372                 }
 373                 ctx.beginPath();
 374                 ctx.moveTo(grid_size/2,0);
 375                 ctx.lineTo(grid_size/2,grid_size);
 376                 ctx.closePath();
 377                 ctx.stroke();
 378
 379                 ctx.beginPath();
 380                 ctx.moveTo(0, grid_size/2);
 381                 ctx.lineTo(grid_size,grid_size/2);
 382                 ctx.closePath();
 383                 ctx.stroke();
 384                 i++;
 385         }
 386         ctx.strokeStyle = "#000";
 387         ctx.lineWidth = 1;
 388         ctx.beginPath();
 389         ctx.moveTo(0, 0);
 390         ctx.lineTo(0,grid_size);
 391         ctx.lineTo(grid_size,grid_size);
 392         ctx.lineTo(grid_size,0);
 393         ctx.lineTo(0,0);
 394         ctx.closePath();
 395         ctx.stroke();
 396 }
 397
 398 /* clear this square by setting area to white */
 399 function clear_square(){
 400         ctx.fillStyle = "#fff";
 401         ctx.fillRect(1,1,grid_size-2,grid_size-2);
 402 }
 403
 404 /* canvas has been clicked find out which grid and make correct change to square if needed. */
 405 function cnvs_clicked(e){}
 406
 407 </script>
 408
 409 <style type="text/css">
 410
 411 </style>
 412
 413 <body onLoad="init_form();">
 414
 415 <div id="topsection">
 416 <!--
 417 <center>
 418 <button onClick='reset();'><img src="http://opentextbook.info/icons/32x32/resultset_first.png" title="Restart" alt="Restart"></button>
 419 &nbsp;&nbsp;
 420 <button onClick='step_back();'><img src="http://opentextbook.info/icons/32x32/resultset_previous.png" title="Step Back" alt="Step Back"></button>
 421 &nbsp;&nbsp;
 422 <button onClick='step_next();'><img src="http://opentextbook.info/icons/32x32/resultset_next.png" title="Next Step" alt="Next Step"></button>
 423 &nbsp;&nbsp;
 424 <button onClick='run();'><img src="http://opentextbook.info/icons/32x32/resultset_last.png" title="Run" alt="Run"></button>
 425 &nbsp;&nbsp;
 426
 427 <!--
 428 <button onClick='halt();'><img src="http://opentextbook.info/icons/32x32/cancel.png" title="Halt Execution" alt="Halt Execution"></button>
 429 &nbsp;&nbsp;
 430
 431 <button disabled><img src="http://opentextbook.info/icons/32x32/disk.png" title="Save Code" alt="Save Code"></button>
 432 &nbsp;&nbsp;
 433 <button onClick='display_docs();'><img src="http://opentextbook.info/icons/32x32/book_open.png" title="Open Documentation" alt="Open Documentation"></button>
 434 -->
 435 </center>
 436
 437 </div>
 438
 439 <div id="xycoordinates">Coordinates:</div>
 440 <canvas id="input" width="579" height="100"></canvas>
 441 <canvas id="stage" width="579" height="770" onmousemove="cnvs_get_coordinates(event)" onclick="cnvs_clicked(event);">
 442 Your browser does not support HTML5 Canvas.
 443 </canvas>
 444
 445 </body>
 446 </html>