Hire the author: Martin K

Check out the Automata Theory image and GitHub Link for this project.

Introduction

Automata Theory is an important computer science subject with many practical applications, such as natural language processing and compiler design. However, understanding the theory is not enough, students must be able to apply the theory in real-world scenarios. The goal is to build a web-based canvas tool for testing Automata Theory applications. It is a practical and interactive tool to help students learn how to apply the theory. The tool allows users to test their ability to develop equivalent NFA/DFA for a given regular expression.

Photo Preview

Automata

Glossary

  • Automata Theory: Branch of computer science and mathematics that studies abstract machines and their computational capabilities.
  • Formal Languages: Rules for constructing strings of symbols that you can use to describe and define programming languages, communication protocols, and other formal systems.
  • Regular Expression: Sequence of characters that define a search pattern, typically used for matching and manipulating text in various programming languages and text editors.
  • NFA (Nondeterministic Finite Automaton): A finite state machine that can be in several states simultaneously and transition to multiple states on the same input symbol.
  • DFA (Deterministic Finite Automaton): A finite state machine that can be in only one state at a time and transition to a single state on each input symbol.

Step-by-Step Procedure 

Step 1: Setting up the HTML structure and CSS files

  1. Open a text editor and create a new file with the extension “.html.”
  2. Copy the following code and paste it into the new file:
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="stylesheet" href="styles.css">
<script type="text/javascript" src="script.js" defer></script>
<title>FLAT Designer</title>
</head>
<body class="no-select">
<h1>AT-AT</h1>
<h2>Automata Theory – Application Tester</h2>
<div class="centre">
<button onclick="gen()" id="regex-generator" type="button">Generate New Regex</button>
<p id="regex"></p>
</div>
<div class="centre">
<canvas id="flat-canvas" width="1000" height="500" style="border:1px solid #000000;">
</canvas>
</div>
<div class="centre">
<p id="result"></p>
<button onclick="comp()" id="fsm-check" type="button">Check For Equivalence With Regex</button>
</div><br>
<div class="centre">
<input type="checkbox" id="dfa-toggle" name="dfa">
<label for="dfa-toggle"> Force DFA Constraint</label>
</div>
<div>
Controls
<ul>
<li><b>Create State:</b> Double-click empty space</li>
<li><b>Create Transition From Highlighted State:</b> Shift-click state to point at</li>
<li><b>Highlight State/Transition:</b> Single-click state/transition</li>
<li><b>Delete State/Transition:</b> Delete key</li>
<li><b>Toggle Start State:</b> Ctrl-click state</li>
<li><b>Toggle Accept State:</b> Double-click state</li>
<li><b>Label Highlighted State/Transition:</b> Type (use '\e' for ε)</li>
</ul>
</div>
</body>
</html>
view raw index.html hosted with ❤ by GitHub

This code includes the basic HTML5 structure, the page title, and some basic elements such as headers, buttons, canvases, and input fields. It also includes links to a stylesheet and a JavaScript file. The code creates the basic skeleton for the web page and sets up the framework for the subsequent steps.

  1. Save the file with a name of your choice, for example, “index.html.”
  2. Create a new file in the same directory named “styles.css” and add the necessary CSS styles, as shown below.
h1,h2,div.centre {
text-align: center;
}
.no-select {
user-select: none;
}
view raw style.css hosted with ❤ by GitHub
  1. Create another new file in the same directory named “script.js” and add any necessary JavaScript code for your webpage.

Step 2: Generating a Regular Expression

We’ll start by creating a class called Regex with a method generate() to generate a random regular expression and its corresponding NFA. The generate() method will call a private method #kleene(), which will create a random regular expression using a probabilistic method. You will store the generated regular expression in the regex property and its postfix notation in the postfix property.

class Regex {
constructor() {
this.generate();
}
/**
* Generate new regular expression and corresponding NFA
*/
generate() {
this.postfix = "";
this.regex = this.#kleene(7, 0.5, 0.2, 0.1);
this.nfa = this.#regexToNfa(this.postfix);
}
/**
* Convert regular expression into equivalent NFA using Thompson's construction
* @param {String} regex A regular expression in postfix
* @returns {
* Array<{
* table:
* Array<{
* stateID: Number,
* symbol: String,
* stateIDs: Array<Number>
* }>,
* start: Number,
* end: Array<Number>
* }>
* } State transition table for NFA accepting regex
* (alongside start state and accept states)
*/
#regexToNfa(regex) {
// …
}
/**
* Generate a random regular expression using probabilistic methods
* @param {Number} n Maximum depth of the regular expression tree
* @param {Number} p Literal probability
* @param {Number} s Concatenation probability
* @param {Number} k Kleene star probability
* @returns {String} Random regular expression
*/
#kleene(n, p, s, k) {
// …
}
}
view raw script.js hosted with ❤ by GitHub

Step 3. Testing the Regular Expression and NFA

Once we have generated the regular expression and corresponding NFA, we can test them with different inputs to see if they behave as expected.

To test the regular expression, we can use the built-in test method of the RegExp class. This method takes a string as input and returns a boolean indicating whether the string matches the regular expression. For example, to test if the regular expression matches the string “hello”, we can use the following code:

const regex = new RegExp(this.regex);
const str = "hello";
const match = regex.test(str);
console.log(match); // true or false
view raw script.js hosted with ❤ by GitHub

We can simulate the NFA’s behavior by iterating through the input string and following the state transitions based on the symbols in the string. If we reach the accept state at the end of the string, the NFA accepts the string. Otherwise, the string will be rejected. Here’s an example of how to use the Simulate method:

/** * Simulate the NFA on a given string * @param {String} str The input string to test * @returns {Boolean}
Whether the NFA accepts the string or not */ simulate(str) { var current = [this.nfa[this.start]]; //
Current set of states for (var i=0; i<str.length; i++) { var next = [];
// Find all states reachable from current states with input symbol for (var state of current)
{ var transitions = state[str[i]]; if (transitions) { for (var s of transitions)
{ if (!next.includes(this.nfa[s])) { next.push(this.nfa[s]); } } } } current = next; }
// Check if any accept state is reachable from current states for (var state of current)
{
if (this.end.includes(state))
{ return true;}
} return false;
}
view raw script.js hosted with ❤ by GitHub

This method can test whether the NFA accepts or rejects a given string. For example, to test if the NFA accepts the string “hello”, we can use the following code:

const match = this.simulate("hello"); console.log(match); // true or false
view raw script.js hosted with ❤ by GitHub

Step 4. Putting it all Together

Now that we have all the pieces in place, we can create an instance of the Regex class and generate a regular expression and corresponding NFA. We can then test the regular expression and NFA with different inputs to see if they behave as expected. Here is an example of usage:

const regex = new Regex();
const str = "hello";
const match1 = regex.test(str);
// true or false
const match2 = regex.simulate(str);
// true or false
console.log(match1, match2);
view raw script.js hosted with ❤ by GitHub

The above will generate a random regular expression and corresponding NFA and test them with the input string “hello”. The test method of the RegExp class will return true if the regular expression matches the string, and the simulated method of the Regex class will return true if the NFA accepts the string.

Step 5: Drawing Edges in a Finite State Machine (FSM) Diagram

This subsection contains JavaScript code that creates an “Edge” class and its methods. The “Edge” class represents an edge that connects two nodes (i.e., states) in a finite state machine diagram. The “draw” method of the “Edge” class draws the edge on a canvas using the 2D rendering context for the drawing surface of the FSM canvas. The method handles three cases: self-loop, curved edge, and straight edge. For each case, the method calculates the positions and angles of the edge and draws it on the canvas. Finally, it draws the label of the edge on the canvas using the third point created.

class Edge {
constructor(id, fromNode, toNode) {
this.id = id;
this.fromNode = fromNode;
this.toNode = toNode;
this.label = "";
// Set if self loop
this.x = null;
this.y = null;
this.radius = null;
// Set if non self loop
this.angle = null;
// Set if curved
this.curved = false;
}
/**
* Draws edge to canvas
* @param {CanvasRenderingContext2D} ctx 2D rendering context for drawing surface of FSM canvas
*/
draw(ctx) {
ctx.strokeStyle = BLACK;
ctx.fillStyle = BLACK;
// Colour edge red if highlighted
if (this.id == highTid) {
ctx.strokeStyle = RED;
ctx.fillStyle = RED;
}
ctx.beginPath();
if (this.fromNode == this.toNode) { // self loop
this.angle = 5*Math.PI/16;
var dx = Math.cos(this.angle)*RADIUS;
var dy = Math.sin(this.angle)*RADIUS;
var xn = this.fromNode.x;
var yn = this.fromNode.y;
// Start of arc
var x1 = xn–dx;
var y1 = yn–dy;
// End of arc
var x2 = xn+dx;
var y2 = yn–dy;
// Arc turning point
var x3 = xn;
var y3 = yn–1.7*RADIUS;
// Find circle equation from three points (above)
var circle = circleFromPoints(x1, y1, x2, y2, x3, y3);
this.x = circle.x; // x centre
this.y = circle.y // y centre
this.radius = circle.radius;
// Angle between arc centre and end of arc
var alpha = Math.atan2(y2–this.y, x2–this.x);
ctx.beginPath();
ctx.arc(this.x, this.y, this.radius, Math.PI–alpha, alpha); // arc is drawn outside of node area
ctx.stroke();
// Draw chevron at end of arc
ctx.beginPath();
ctx.moveTo(x2, y2);
ctx.lineTo(x2+CHEVRON*Math.cos(this.angle–Math.PI/10), y2–CHEVRON*Math.sin(this.angle–Math.PI/10));
ctx.lineTo(x2–CHEVRON*Math.cos(this.angle+Math.PI/10), y2–CHEVRON*Math.sin(this.angle+Math.PI/10));
ctx.closePath();
ctx.stroke();
ctx.fill();
ctx.strokeStyle = BLACK; // revert colour to black
ctx.fillStyle = STATEFILL;
var width = ctx.measureText(this.label).width;
ctx.fillRect(x3–width/2, y3–4–FONTSIZE+2, width, FONTSIZE+2);
ctx.fillStyle = BLACK;
ctx.beginPath();
ctx.fillText(this.label, x3, y3–4);
ctx.stroke();
ctx.fillStyle = STATEFILL
} else if (this.curved) { // curved edge between nodes
var x1 = this.fromNode.x;
var y1 = this.fromNode.y;
var x2 = this.toNode.x;
var y2 = this.toNode.y;
var dx = x1–x2;
var dy = y1–y2;
this.angle = Math.atan2(dy, dx);
var x3 = 0.5*(x1+x2) + 2*SELECTAREA*Math.cos(this.angle – Math.PI/2);
var y3 = 0.5*(y1+y2) + 2*SELECTAREA*Math.sin(this.angle – Math.PI/2);
// create circle using three points
var circle = circleFromPoints(x1, y1, x2, y2, x3, y3);
var xc = circle.x;
var yc = circle.y;
// only draw section between nodes
var startAngle = Math.atan2(y2–yc, x2–xc);
var endAngle = Math.atan2(y1–yc, x1–xc);
ctx.beginPath();
ctx.arc(xc, yc, circle.radius, startAngle, endAngle);
ctx.stroke();
// get coords of arc intersection with 'to' node
var alpha = Math.acos(RADIUS/(2*circle.radius)) – startAngle + Math.PI;
var xi = x2 + RADIUS*Math.cos(alpha);
var yi = y2 – RADIUS*Math.sin(alpha);
var beta = Math.atan2(yi–y2,xi–x2);
// dynamically draw chevron
ctx.beginPath();
ctx.moveTo(xi, yi);
ctx.lineTo(xi+CHEVRON*Math.cos(beta–Math.PI/5), yi+CHEVRON*Math.sin(beta–Math.PI/5));
ctx.lineTo(xi+CHEVRON*Math.cos(beta+Math.PI/5), yi+CHEVRON*Math.sin(beta+Math.PI/5));
ctx.closePath();
ctx.stroke();
ctx.fill();
ctx.strokeStyle = BLACK; // revert colour to black
// draw the label at the third point that was created
ctx.fillStyle = STATEFILL;
var width = ctx.measureText(this.label).width;
ctx.fillRect(x3–width/2, y3–FONTSIZE+2, width, FONTSIZE+2);
ctx.fillStyle = BLACK;
ctx.beginPath();
ctx.fillText(this.label, x3, y3);
ctx.stroke();
ctx.fillStyle = STATEFILL;
} else {
if (this.id == startTid) { // start edge
var toX = this.toNode.x–RADIUS;
var toY = this.toNode.y;
var fromX = toX–RADIUS;
var fromY = toY;
var dx = RADIUS;
var dy = 0;
this.angle = Math.atan2(dy, dx);
} else { // edge between nodes
var toX = this.toNode.x;
var toY = this.toNode.y;
var fromX = this.fromNode.x;
var fromY = this.fromNode.y;
// Calculates line angle between centres of each node
var dx = toX–fromX;
var dy = toY–fromY;
this.angle = Math.atan2(dy, dx);
// 'Remove' portion of edge contained within nodes
fromX += Math.cos(this.angle)*RADIUS;
fromY += Math.sin(this.angle)*RADIUS;
toX -= Math.cos(this.angle)*RADIUS;
toY -= Math.sin(this.angle)*RADIUS;
}
// Draw connecting line
ctx.beginPath();
ctx.moveTo(fromX, fromY);
ctx.lineTo(toX, toY);
ctx.stroke();
// Draw chevron at end of edge
ctx.beginPath();
ctx.moveTo(toX, toY);
ctx.lineTo(toX–CHEVRON*Math.cos(this.angle – Math.PI/6), toY–CHEVRON*Math.sin(this.angle – Math.PI/6));
ctx.lineTo(toX–CHEVRON*Math.cos(this.angle + Math.PI/6), toY–CHEVRON*Math.sin(this.angle + Math.PI/6));
ctx.closePath();
ctx.stroke();
ctx.fill();
ctx.strokeStyle = BLACK; // revert colour to black
ctx.fillStyle = STATEFILL;
if (this.fromNode != null) {
var width = ctx.measureText(this.label).width;
var x = (this.fromNode.x + this.toNode.x) / 2;
var y = (this.fromNode.y + this.toNode.y) / 2;
ctx.fillRect(x–width/2, y–FONTSIZE+2, width, FONTSIZE+2);
ctx.fillStyle = BLACK;
ctx.beginPath();
ctx.fillText(this.label, x, y);
ctx.stroke();
ctx.fillStyle = STATEFILL;
}
}
}
}
view raw script.js hosted with ❤ by GitHub

Learning Tools

I found several resources helpful when building this tool, including:

Learning Strategy

I faced several challenges when building this tool, particularly in understanding how to convert regular expressions to NFA/DFA and how to implement canvas operations in JavaScript. To overcome these obstacles, I experimented with various learning techniques, including reading books and articles on automata theory, taking online courses on JavaScript and canvas operations, seeking help from online forums and communities like Stack Overflow, collaborating with more experienced colleagues, and trying out different libraries and tools. While all these methods were helpful, collaborating with more experienced colleagues was the most effective approach for me. Their guidance and mentorship proved invaluable in navigating the challenges I faced.

Reflective Analysis

After completing this project, I have a deeper understanding of Automata Theory and its applications. I can now create an equivalent NFA/DFA for a given regular expression and understand how to verify their equivalence. This project has provided me with a practical and interactive learning experience, making it easier to understand and apply the theory. What separates ordinary people from experts in the field is their ability to apply theory to real-world problems and create effective solutions.

Conclusions and Future Directions

In conclusion, the Automata Theory testing app is a practical and interactive tool for testing the application of Automata Theory. Future directions for this project include expanding the tool’s features to test other aspects of Automata Theory and incorporating more feedback and analytics for a more comprehensive learning experience. Remember to check out the GitHub repository for this project.

Hire the author: Martin K