A Cellular Automaton is a discrete model similar to any other automaton which has its own start state(s) and a set of rules.
A cellular automaton is a model of a system of “cell” objects with the following characteristics :
- The cells live on a grid which can be either 1D or even multi-dimensional
- Each cell has a state. The number of state possibilities is typically finite. The simplest example has the two possibilities of 1 and 0
- Each cell has a neighbourhood and it is typically a list of adjacent cells
Working principle of Cellular Automata?
The working principle of the cellular automata is shown below:
- An initial state is selected by assigning a state for each cell.
- A new generation is created, according to some fixed rule that determines the new state of each cell in terms of:
- The current state of the cell.
- The states of the cells in its neighbourhood.
- Hence, a new state is calculated by looking at all previous neighbouring states.
Examples of Cellular Automata:
2. Rule 90:
Rule 90 is an elementary cellular automaton that consists of a one-dimensional array of cells, each of which can hold either a 0 or a 1 value. Each cell is the exclusive or(XOR) of its two neighbours.
| Current State | 111 | 011 | 101 | 100 | 011 | 010 | 001 | 000 |
| Next State | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
If we concatenate the Next State into a single binary number and convert it to decimal (01011010)2, it becomes 90, hence we get the name Rule 90.
3. When the initial state has a single nonzero cell, this diagram has the appearance of the Sierpiński triangle.
Implementation of Sierpiński triangle:
C++
// C++ code to implement Sierpinski Triangle#include <bits/stdc++.h>using namespace std;// Length of the string used as a "Seed"#define LENGTH 34// How many lines the program will generateint n = 15;// All the patterns possiblevector<vector<int> > rules = { { 0, 0, 0 }, { 0, 0, 1 }, { 0, 1, 0 }, { 0, 1, 1 }, { 1, 0, 0 }, { 1, 0, 1 }, { 1, 1, 0 }, { 1, 1, 1 } };// Utility Function to Print Rulesvoid printRules(){ int i, j; cout << "The rules of Rule 90 Cellular Automaton" " are as follows: \n"; for (i = 0; i < 8; i++) { cout << "\t\tRule " << i + 1 << ": "; for (j = 0; j < 3; j++) cout << rules[i][j] << " "; cout << "-> sets cell to: " << (rules[i][0] ^ rules[i][2]) << "\n"; }}// Print the Current Statevoid outState(vector<int> s){ cout << "\t\t"; for (int i = 0; i < LENGTH; i++) { if (s[i] == 1) cout << "\u25A0"; else if (s[i] == 0) cout << " "; } cout << "\n";}// Function to print the trianglevoid utilize(){ // Initialize starting state // to sierpinski triangle vector<int> sierpinski(LENGTH); vector<int> updateState(LENGTH); sierpinski[(LENGTH) / 2 - 1] = 1; // Print Sierpinski Triangle // initial String outState(sierpinski); // Loop to generate/update the state // and update state arrays for (int i = 0; i < n; i++) { // Erase the old state updateState.assign(LENGTH, 0); // Create the new state for (int j = 1; j < LENGTH - 1; j++) { int f1 = sierpinski[j - 1]; int f2 = sierpinski[j]; int f3 = sierpinski[j + 1]; // Create an array with the // current pattern vector<int> current; current.push_back(f1); current.push_back(f2); current.push_back(f3); // XOR the current state's neighbours // to set the cell's value // in Update State updateState[j] = current[0] ^ current[2]; } // Update the current state sierpinski.assign(updateState.begin(), updateState.end()); // Print the new current state outState(sierpinski); }}// Driver codeint main(){ // Print out the rules for // rule 90 cellular Automaton printRules(); cout << "\n\t\t\tSIERPINSKI TRIANGLE\n\n"; utilize(); return 0;} |
Output
The rules of Rule 90 Cellular Automata are as follows:
Rule 1: 0 0 0 -> sets cell to: 0
Rule 2: 0 0 1 -> sets cell to: 1
Rule 3: 0 1 0 -> sets cell to: 0
Rule 4: 0 1 1 -> sets cell to: 1
Rule 5: 1 0 0 -> sets cell to: 1
Rule 6: 1 0 1 -> sets cell to: 0
Rule 7: 1 1 0 -> sets cell to: 1
Rule 8: 1 1 1 -> sets cell to: 0
SIERPINSKI TRIANGLE
■
■ ■
■ ■
■ ■ ■ ■
■ ■
■ ■ ■ ■
■ ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ■
■ ■
■ ■ ■ ■
■ ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
