#Automaton simulator simulator

Typical characteristics of a CA are the following: These rules can be iteratively applied for as many time steps as required. Additionally, the cells in a grid evolve in parallel at discrete time steps by considering the states of neighboring cells.Īs a result, the evolution of the CA through several discrete time steps occurs based on a set of rules founded on the states of neighboring cells. A CA is discrete in both space and time, which means that in each time unit, the cells that constitute the CA represent one of a finite set of states. Abstract refers to the fact that a CA can be specified in purely mathematical terms. This computational model is both abstract and spatially and temporally discrete.Ĭomputational means the model can compute functions and solve algorithmic problems. Each cell is in one of a finite number of states. Characteristics of a cellular automatonĪ CA is a collection of colored cells or atoms on a grid of a specified shape. CAs have been suggested for possible use in public key cryptography, as well as for applications in geography, anthropology, political science, sociology and physics, among others. We'll see if I get around to it someday.A cellular automaton (CA) is a collection of cells arranged in a grid of specified shape, such that each cell changes state as a function of time, according to a defined set of rules driven by the states of neighboring cells. It wouldn't be very involved, but it would challenge the user to build a machine for a certain language and help them make the connections between these machines and regular expressions. Something I'd like to do in the future is to build a simple game around the site. I had fun creating the site and hopefully CS students will find it useful in developing their understanding of finite-state machines. You can debug a machine by stepping through an input and you can bulk test a large set of strings with a single button press. A small set of examples is included on the site. Or you can copy/paste machine descriptions to share with other people. You can save/load machines from your browser's local storage. I took my Python simulators, rewrote them in Javascript, and built a lovely UI around them. Then I'd encode each student's machine into my simulator, run a bunch of tests and figure out from there whether it worked and, if not, how badly it was wrong.Ī is a fully functional tool to visually create and test these types of machines.

#Automaton simulator simulator

So to aid my grading I wrote a simple simulator in Python for each machine type. Drawing out machines, tracing through their execution, finding bugs, and making sure they did what they were supposed to without doing things they weren't supposed to.Īs the TA I had to grade a lot of these messily drawn machines that often didn't work. Well, we had to do all this work by hand. They're usually quite meaningless in and of themselves, but the point is to develop the skills necessary to understand how programming languages are created and why, as well as to hone the ability to logically analyze problems and build logically consistent solutions. Or, make a machine that will accept strings that have the same number of 'A's as 'B's.

For example, make a machine that will accept strings that alternate between 'A' and 'B'. This usually means developing a working automaton design based on some desired language recognition. In the CS course I TA'd for as a student, CS 252, a chunk of the course is devoted to working with these concepts. And Push-Down Automata (PDA) can process any Context-Free Grammars.

For example, Deterministic Finite Automata (DFA) can be used to process any Regular Language (i.e., regular expressions, which are infinitely useful). They are equivalent to various useful language concepts. In Computer Science we study simple automatons called finite-state machines.