JustToThePoint English Website Version
JustToThePoint en español
JustToThePoint in Thai

Game of Life and Automatons. Rock Paper Scissors Cellular Automata.

Life is a challenge, meet it! Life is a dream, realize it! Life is a game, play it! Life is love, enjoy it! — Sathya Sai Baba

Life is a challenge, meet it!

Life is a challenge, meet it!

The Game of Life is “a cellular automaton devised by John Horton Conway in 1970. It is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further input. One interacts with the Game of Life by creating an initial configuration and observing how it evolves,” Consway’s Game of Life, Wikipedia entry.

It simulates the evolution of life on a two-dimensional plane or grid. Each next state of the world is uniquely determined by the current state and a very simple set of rules, applied simultaneously to all the cells of the grid.

import pygame
import numpy as np
ALIVE = True
DEATH = False
LIVE_COLOR = (255, 255, 255)
DEATH_COLOR = (50, 50, 50)
OFFSET = 1

class GameofLife:
    def __init__(self, surface, width=1920, height=1080, scale=10):
        self.surface = surface
        self.width = width
        self.height = height
        self.scale = scale
        self.columns = int(height / scale)
        self.rows = int(width / scale)
        # The universe is a two-dimensional grid of cells, each of which is in one of two possible states: alive or dead.
        self.grid = np.random.randint(0, 2, size=(self.rows, self.columns), dtype=bool) # It generates a self.rows x self.columns two-dimensional array of booleans. 
        self.grid = np.where(self.grid==False, DEATH, ALIVE) # This line's purpose is to make the code easy to read.

    def draw_grid(self):
        """It draws the grid"""
        for row in range(self.rows):
            for col in range(self.columns):
                if self.grid[row, col]==ALIVE:
                    pygame.draw.rect(self.surface, LIVE_COLOR, [row * self.scale, col * self.scale, self.scale - OFFSET, self.scale - OFFSET])
                else:
                    pygame.draw.rect(self.surface, DEATH_COLOR, [row * self.scale, col * self.scale, self.scale - OFFSET, self.scale - OFFSET])
    
    def update_grid(self):
        """ It updates the grid using Conway's game of life rules."""
        updated_grid = copy.deepcopy(self.grid)
        for row in range(self.rows):
            for col in range(self.columns):
                updated_grid[row, col] = self.update_cell(row, col)

        self.grid = updated_grid

    def num_alive_neighbors(self, x, y):
        """ It returns the number of the cell's (self.grid[x, y]) neighbors that are alive."""
        alive_neighbors = 0
        for i in range(-1, 2):
            for j in range(-1, 2):
                if i == 0 and j == 0: # The cell does not count itself as a neighbour. I am not my neighbour!
                    continue
                elif (x+i)<0 or (x+i)>=self.rows or (y+j)<0 or (y+j)>=self.columns: # The "neighbour" cell needs to be on the grid.
                    continue
                elif self.grid[x + i, y + j]==ALIVE: # The "neighbour" cell needs to be alive.
                    alive_neighbors += 1
                
        return alive_neighbors

    def update_cell(self, x, y):
        """ It updates the cell based on Conway's game of life rules."""
        current_state = self.grid[x, y]
        alive_neighbors = self.num_alive_neighbors(x, y)
        
        # Any alive cell with fewer than 2 alive neighbor cells dies as if caused by solitude or isolation.
        if current_state==ALIVE and alive_neighbors < 2:                                       
            return False
        # Any alive cell with 2 or 3 alive neighbor cells survives, so it lives on to the next generation.
        elif current_state==ALIVE and (alive_neighbors == 2 or alive_neighbors == 3):        
            return True
        # Any alive cell with more than three alive neighbor cells dies, as if caused by overpopulation.
        elif current_state==ALIVE and alive_neighbors > 3:                                     
            return False
        # Any death cell with three alive neighbor cells becomes alive, as if caused by reproduction.
        elif current_state==DEATH and alive_neighbors == 3:                                  
            return True
        else:
            return current_state

The Game class

import sys
import pygame
from pygame.locals import *
from game_of_life import GameofLife
WIDTH = 1280
HEIGHT = 1024

class Game: # It represents the game itself
    def __init__(self):
        pygame.init()  # It initializes all imported pygame modules.
        pygame.display.set_caption("Conway's Game of Life") # It sets the current window tittle.
         # It sets the display mode and creates an instance of the pygame.Surface class.
        self.screen = pygame.display.set_mode((WIDTH, HEIGHT)) 
        self.conway = GameofLife(self.screen, scale=13)
        self.clock = pygame.time.Clock()  # A pygame.time.Clock object helps us to make sure our program runs at a certain FPS.
        self.fps = 60 # This is our frame rate. It is expressed in frames per second or FPS. It is the frequency or rate at which consecutive images or frames are captured or displayed in the game.
        self.running = True # It indicates that the game is still running.

The method game_loop controls the overall flow for the entire game program. There are three tasks: 1. Check all events. 2. Process these events and take action accordingly. 3. Draw the current state of the game so the player can see what is going on.

    def gameLoop(self):
        self.clock.tick(self.fps) # It keeps the game running at a constant FPS. 
        self.screen.fill((0, 0, 0)) # It fills the whole screen with black.
        self.checkEvents() # It checks all the events.
        self.conway.draw_grid() # It draws our grid or universe.
        self.conway.update_grid() # It updates our grid or universe.
        pygame.display.update() # It updates the full display surface to the screen.

    def checkEvents(self): # Pygame handles all its event messaging through an event queue. This method checks all these events.
        for event in pygame.event.get(): # It gets events from the queue.
            if event.type == pygame.QUIT:
                self.running = False

            if event.type == KEYDOWN: # A key is physically pressed on.
                    if event.key == K_ESCAPE: # The ESC key was pressed.
                        self.running = False

if __name__ == '__main__':
    game = Game() # The main function is quite simple. We create an instance of our Game class.
    while game.running: # It loops while the game is still running.
        game.gameLoop() # We call the game's game_loop function.

    pygame.quit()
    sys.exit()
Game of Life

Game of Life

Rock Paper Scissors Cellular Automata

Rock Paper Scissors is a “hand game in which each player simultaneously forms one of three shapes with an outstretched hand. These shapes are “rock” (a closed fist), “paper” (a flat hand), and “scissors” (a fist with the index finger and middle finger extended, forming a V). A player who decides to play rock will beat another player who has chosen scissors (“rock crushes scissors”), but will lose to one who has played paper (“paper covers rock”); a play of paper will lose to a play of scissors (“scissors cuts paper”). If both players choose the same shape, the game is tied,” Wikipedia entry.

Converting the game to a cellular automaton is quite simple. Every pixel is calculated by playing a virtual game of rock paper scissors between each cell and its neighbors. If the number of neighbors that beats the current cell is greater than a threshold value, let’s say three, then the current cell becomes the winner. For example, if the current cell is scissors and there are 4 rocks surrounding it, then it becomes a rock.

We implement every pixel in our grid as a cell. Every cell has a status (alive or dead), id (rock, paper, and scissors), and color.

import pygame
import numpy as np
import random
import copy
ALIVE = True
DEATH = False
OFFSET = 1

class Cell:
    def __init__(self, id):  
        self.status = ALIVE
        self.changeId(id)
        
    def changeId(self, newId = None):
        if newId==None:
            self.id = random.randint(0, 2)
        else:
            self.id = newId

        self.color = [(255,0,0), (0,0,255), (255,255,0)][self.id]
        
    def isAlive(self):
        return self.status == ALIVE

    def __str__(self) -> str:
        return str(self.status) + "," + str(self.id)

    def copy(self, status):
        myCopy = Cell(self.id)
        myCopy.status = status
        return myCopy

A cell’s id is self.id (let’s say paper), its predator’s id is (self.id + 1) % 3 -scissors-, and its prey is (self.id + 2) % 3 -rock-.

    def isPredator(self, neighbor):
        return neighbor.id==(self.id + 1) % 3

    def isPrey(self, neighbor):
        return neighbor.id==(self.id + 2) % 3

    def turnPrey(self):
        myCopy = Cell( (self.id + 2) % 3 )
        myCopy.status = self.status
        return myCopy

    def turnPredator(self):
        myCopy = Cell( (self.id + 1) % 3 )
        myCopy.status = self.status
        return myCopy

class GameofLife:
    def __init__(self, surface, width=1920, height=1080, scale=10):
        self.surface = surface
        self.width = width
        self.height = height
        self.scale = scale
        self.columns = int(height / scale)
        self.rows = int(width / scale)
        # The _universe is a two-dimensional grid of cells_, each of which is in one of two possible states: alive or dead.
        self.grid = [[Cell((c+r)%3) for c in range(self.columns)] for r in range(self.rows)]
        
    def draw_grid(self):
        """ It draws the grid."""
        for row in range(self.rows):
            for col in range(self.columns):
                if self.grid[row][col].isAlive():
                    pygame.draw.rect(self.surface, self.grid[row][col].color, [row * self.scale, col * self.scale, self.scale - OFFSET, self.scale - OFFSET])
                else: # It is not really necessary, all cells on the grid are alive.
                    pygame.draw.rect(self.surface, DEATH_COLOR, [row * self.scale, col * self.scale, self.scale - OFFSET, self.scale - OFFSET])
    
    def update_grid(self):
        """ It updates the grid based on Rock Paper and Scissors rules."""
        updated_grid = copy.deepcopy(self.grid)
        for row in range(self.rows):
            for col in range(self.columns):
               updated_grid[row][col] = self.update_cell(row, col)

        self.grid = updated_grid

    def cell_neighbors(self, x, y):
        """ It returns the number of the current or active cell's (self.grid[x, y]) neighbors that are predators and the number of its neighbors that are prey."""
        predators_neighbors = 0
        prey_neighbors = 0

        for i in range(-1, 2):
            for j in range(-1, 2):
                if i == 0 and j == 0: # The cell does not count itself as a neighbour. I am not my neighbour!
                    continue
                elif (x+i)<0 or (x+i)>=self.rows or (y+j)<0 or (y+j)>=self.columns: # The neighbour cell needs to be on the grid.
                    continue
                elif self.grid[x + i][y + j].isAlive() and self.grid[x][y].isPredator(self.grid[x + i][y + j]): # If the neighbour cell is alive and it is one of the current cell predators, we increase the variable predators_neighbors by 1.
                    predators_neighbors += 1
                elif self.grid[x + i][y + j].isAlive() and self.grid[x][y].isPrey(self.grid[x + i][y + j]): # If the neighbour cell is alive and it is one of the current cell preys, we increase the variable prey_neighbors by 1.
                    prey_neighbors += 1
        
        return predators_neighbors, prey_neighbors

    def update_cell(self, x, y):
        """ It updates the current or active cell based on Rock Paper and Scissors rules."""
        predators_neighbors, prey_neighbors = self.cell_neighbors(x, y)
        current_state = self.grid[x][y].status

Rather than checking if the winning neighbor count (the number of the current cell neighbors that are predators) is greater than a specified threshold, we are going to check if it is greater than a threshold plus a small random amount (random.randint(0, 2)). Biology is inherently random, so we are trying to insert some randomness into the model.

        threshold = 3 + random.randint(0, 2)

        if current_state==ALIVE and predators_neighbors >= threshold:
            return self.grid[x][y].turnPredator()
        elif current_state==ALIVE and prey_neighbors >= threshold:
            return self.grid[x][y].turnPrey()
        else:
            return self.grid[x][y].copy(current_state)
Rock Paper Scissors Cellular Automata

Rock Paper Scissors Cellular Automata

Rock Paper Scissors Lizard Spock Cellular Automata

How does it work? Oh, it’s very simple. Scissors cuts paper, paper covers rock, rock crushes lizard, lizard poisons Spock, Spock smashes scissors, scissors decapitates lizard, lizard eats paper, paper disproves Spock, Spock vaporizes rock, and as it always has, rock crushes scissors, The Big Bang Theory

Every pixel is calculated by playing a virtual game of rock paper scissors lizard spoke between each cell and its neighbors. If the number of neighbors that beats the current cell is greater than a threshold value (e.g., 3), then the current cell becomes the winner. For example, if the current cell is scissors and there are 4 rocks and spocks surrounding it, then it becomes a rock or a spock.

We implement every pixel in our grid as a cell. Every cell has a status (alive or dead), id (rock, paper, scissors, spock, and lizard), and color.

import pygame
import numpy as np
import random
import copy
ALIVE = True
DEATH = False
DEATH_COLOR = (50, 50, 50)
OFFSET = 1

class Cell:
    def __init__(self, id):
        self.status = ALIVE
        self.changeId(id)
        
    def changeId(self, newId = None):
        if newId==None:
            self.id = random.randint(0, 4)
        else:
            self.id = newId

        self.color = [(255,0,0), (0,0,255), (255,255,0), (0,255,0), (255,192, 203)][self.id]
        
    def isAlive(self):
        return self.status == ALIVE

    def __str__(self) -> str:
        return str(self.status) + "," + str(self.id)

    def copy(self, status):
        myCopy = Cell(self.id)
        myCopy.status = status
        return myCopy

A cell’s id is self.id (let’s say paper), its predators’ id are (self.id + 1) % 5 -scissors- and (self.id + 2) % 5 -lizard-, and its preys’ id are (self.id + 3) % 5 -rock- and (self.id + 4) % 5 -spock-.

    def isPredator(self, neighbor):
        return neighbor.id==(self.id + 1) % 5 or neighbor.id==(self.id + 2) % 5

    def isPrey(self, neighbor):
        return neighbor.id==(self.id + 3) % 5 or neighbor.id==(self.id + 4) % 5

    def turnPrey(self):
        myCopy = Cell( (self.id + random.randint(3, 4)) % 5 )
        myCopy.status = self.status
        return myCopy

    def turnPredator(self):
        myCopy = Cell( (self.id + random.randint(1, 2)) % 5 )
        myCopy.status = self.status
        return myCopy

class GameofLife:
    def __init__(self, surface, width=1920, height=1080, scale=10):
        self.surface = surface
        self.width = width
        self.height = height
        self.scale = scale
        self.columns = int(height / scale)
        self.rows = int(width / scale)
        # The _universe is a two-dimensional grid of cells_, each of which is in one of two possible states: alive or dead.
        self.grid = [[Cell((c+r)%5) for c in range(self.columns)] for r in range(self.rows)]
        
    def draw_grid(self):
        """ It draws the grid."""
        for row in range(self.rows):
            for col in range(self.columns):
                if self.grid[row][col].isAlive():
                    pygame.draw.rect(self.surface, self.grid[row][col].color, [row * self.scale, col * self.scale, self.scale - OFFSET, self.scale - OFFSET])
                else: # It is not really necessary, all cells on the grid are alive.
                    pygame.draw.rect(self.surface, DEATH_COLOR, [row * self.scale, col * self.scale, self.scale - OFFSET, self.scale - OFFSET])
    
    def update_grid(self):
        """ It updates the grid based on Rock Paper Scissors Lizard and Spock rules."""
        updated_grid = copy.deepcopy(self.grid)
        for row in range(self.rows):
            for col in range(self.columns):
                updated_grid[row][col] = self.update_cell(row, col)

        self.grid = updated_grid

    
    def cell_neighbors(self, x, y):
        """ It returns the number of the current or active cell's (self.grid[x, y]) neighbors that are predators and the number of its neighbors that are prey."""
        predators_neighbors = 0
        prey_neighbors = 0

        for i in range(-1, 2):
            for j in range(-1, 2):
                if i == 0 and j == 0: # The cell does not count itself as a neighbour. I am not my neighbour!
                    continue
                elif (x+i)<0 or (x+i)>=self.rows or (y+j)<0 or (y+j)>=self.columns: # The neighbour cell needs to be on the grid.
                    continue
                elif self.grid[x + i][y + j].isAlive() and self.grid[x][y].isPredator(self.grid[x + i][y + j]): # If the neighbour cell is alive and it is one of the current cell predators, we increase the variable predators_neighbors by 1.
                    predators_neighbors += 1
                elif self.grid[x + i][y + j].isAlive() and self.grid[x][y].isPrey(self.grid[x + i][y + j]): # If the neighbour cell is alive and it is one of the current cell preys, we increase the variable prey_neighbors by 1.
                    prey_neighbors += 1
        
        return predators_neighbors, prey_neighbors

    def update_cell(self, x, y):
        """ It updates the cell based on Rock Paper Scissors Lizard and Spock rules."""
        predators_neighbors, pray_neighbors = self.cell_neighbors(x, y)
        current_state = self.grid[x][y].status
        threshold = 3 + random.randint(0, 2)
        # Rather than checking if the winning neighbor count (the number of the current cell neighbors that are predators) is greater than a specified threshold, we are going to check if it is greater than a threshold plus a small random amount (random.randint(0, 2)).
        
        if current_state==ALIVE and predators_neighbors >= threshold:
            return self.grid[x][y].turnPredator()
        # We can also check if the losing neighbor count is greater than a threshold plus a small random amount, and if this is the case, turn the current or active cell into prey. However, these are different ways of designing our simulation. It is up to you to evaluate and decide which is the best model or rules to be chosen. 
        # elif current_state==ALIVE and pray_neighbors >= threshold:
        #    return self.grid[x][y].turnPrey()
        else:
            return self.grid[x][y].copy(current_state)
Rock Paper Scissors Lizard Spock Cellular Automata

Rock Paper Scissors Lizard Spock Cellular Automata

Deterministic finite automatons in Python

A deterministic finite automaton (DFA) is a finite-state machine that accepts or rejects a given string of symbols, by running through a sequence of states uniquely determined by this particular string. More formally, a deterministic finite automaton M is a 5-tuple, (Q, Σ, δ, q0, F), consisting of:

Deterministic finite automatons in Python. Fig. A

Deterministic finite automatons in Python. Fig. A

In other words, the machine starts in the initial or start state q0. Given each character of an input string “w”, the machine will transition from state to state according to the transition function δ. It will accept the given string “w” if the last character of w causes the machine to halt in one of the accepting states. Otherwise, it is rejected.

dfa = {0: {‘0’:0, ‘1’:1}, # Credits: John Coleman, stackoverflow. Fig. A.1 Automaton. It is a deterministic finite automaton that accepts only binary numbers that are multiples of 3. The transitions are represented by a dictionary of dictionaries. 1:{‘0’:2, ‘1’:0}, 2:{‘0’:1, ‘1’:2}}

def accepts(transitions, initialState, acceptingStates, entryString, alphabet):
    state =  initialState
    for c in entryString:
        if int(c) not in alphabet:
            print("Input error: " + str(c) + " is not in the alphabet.")
            return False

        state = transitions[state][c]
    return state in acceptingStates

if __name__ == '__main__':
    print(accepts(dfa, 0, {0}, '1211101', {0, 1})) # Input error: 2 is not in the alphabet. False.
    print(accepts(dfa, 0, {0}, '1000010', {0, 1})) # True (66 is a multiple of 3)
    print(accepts(dfa, 0, {0}, '1000001', {0, 1})) # False (65 is not a multiple of 3).

Conversion of Regular Expressions to Finite Automata

Regular expressions are used in search engines, search and replace dialogs of word processors and text editors, in text processing utilities such as sed and awk, etc. They are patterns that provides concise and flexible means to specify and recognize strings of text, such as characters, words, or patterns of characters.

Let’s implement an automata to recognize the regular expression ba*b. Fig. A.2:

dfa = {0: {'b': 1},
       1:{'a': 1, 'b': 2},
       2: None}

def accepts(transitions, initialState, acceptingStates, entryString, alphabet):
    state =  initialState
    for c in entryString:
        if c not in alphabet:
            print("Input error: " + str(c) + " is not in the alphabet.")
            return False

        # If there are still characters to be processed by the automaton and there is no dictionary for the current state or there is no key in the dictionary that has "c" as a key, the input string is not valid.
        if transitions[state] is not None and transitions[state].get(c) is not None:
            state = transitions[state][c]
        else:
            print("The input string " + entryString + " is not valid.")
            return False

    return state in acceptingStates

if __name__ == '__main__':
    print(accepts(dfa, 0, {2}, 'b1a', {"a", "b"})) # Input error: 1 is not in the alphabet.
    print(accepts(dfa, 0, {2}, 'baab', {"a", "b"})) # True
    print(accepts(dfa, 0, {2}, 'bbaab', {"a", "b"})) # The input string bbaab is not valid. False.
    print(accepts(dfa, 0, {2}, 'abbaab', {"a", "b"})) # The input string abbaab is not valid. False.

Deterministic Finite Automata in Python using Automata

We are going to use Automata, a Python 3 library which implements the structures and algorithms for finite automata, pushdown automata, and Turing machines.

from automata.fa.dfa import DFA
# DFA which matches all binary strings ending in an odd number of '1's
dfa = DFA(
    states={'q0', 'q1', 'q2'}, # This is a set of the DFA's valid states.
    input_symbols={'0', '1'}, # This is a set of the DFA's valid input symbols.
    transitions={ # This is a dict consisting of the transitions for each state.
        'q0': {'0': 'q0', '1': 'q1'},
        'q1': {'0': 'q0', '1': 'q2'},
        'q2': {'0': 'q2', '1': 'q1'}
    },
    initial_state='q0', # The name of the initial state for this DFA.
    final_states={'q1'} # A set of final states for this DFA.
)

dfa.show_diagram(path='./dfa1.png') # Fig A, dfa1.png. 

if dfa.accepts_input("00111"): # If the input is accepted, it returns True. Otherwise, it returns False.
    print('accepted')
else:
    print('rejected')
Deterministic finite automatons in Python. Figure A

Deterministic finite automatons in Python. Figure A

from automata.fa.dfa import DFA
# DFA that accepts or recognizes the regular expression: a(bc)* (Fig A, dfa2.png)
dfa = DFA(
    states={'q0', 'q1', 'q2'},
    input_symbols={'a', 'b', 'c'},
    transitions={
        'q0': {'a': 'q1'},
        'q1': {'b': 'q2'},
        'q2': {'c': 'q1'}
    },
    initial_state='q0',
    final_states={'q1'},
    allow_partial=True
)

Each DFA state must have a transition to every input symbol by default. However, you can disable this by setting the value of allow_partial to True.

dfa.show_diagram(path='./dfa2.png')

if dfa.accepts_input("abcbc"): # abcbc is accepted, but abcbca and abacbc are rejected.
    print('accepted')
else:
    print('rejected')

from automata.fa.dfa import DFA
# DFA that accepts or recognizes the regular expression: (a+b)c* (Fig. A, dfa3.png)
dfa = DFA(
    states={'q0', 'q1', 'q2'},
    input_symbols={'a', 'b', 'c'},
    transitions={
        'q0': {'a': 'q1', 'b': 'q1'},
        'q1': {'c': 'q2'},
        'q2': {'c': 'q2'}
    },
    initial_state='q0',
    final_states={'q2'},
    allow_partial=True
)

dfa.show_diagram(path='./dfa3.png')

if dfa.accepts_input("acccc"): # accc and bc are accepted, but cadb and abc are rejected.
    print('accepted')
else:
    print('rejected')

An Object-Oriented Implementation of Automaton

We will use two classes: State and Automata. The class State is used to implement all DFA states. The class Automata is designed to model a DFA.

A State consists of an identification symbol (id) and a list of links or transitions to other states. Each link or transition is a tuple consisting of two elements: a symbol and the new state.

class State:
    def __init__(self, id):
        self.id = id
        self.links = []

    def add_link(self, symbol, newState):
        # It adds a new link or transition to the state.
        self.links.append( (symbol, newState) )

    def __eq__(self, otherState):
        # It overloads the == operator.
        if otherState==None: return False
        return self.id == otherState.id
    
    def __str__(self):
        state = "(%s):\n" % self.id
        for (symbol, newState) in self.links:
            state += str(symbol) + " : " + str(newState.id) + "\n"
        return state

class Automata:
    def __init__(self, initial_state, states, terminal_state):
        self.initial_state = initial_state
        self.states = states
        self.terminal_state = terminal_state

    def get_next_state(self, current_state, character):
        for (symbol, newState) in current_state.links:
            if symbol == character:
                return newState
        return None
    
    def accepts(self, string):
        currentState = self.initial_state
        for character in string:
            currentState = self.get_next_state(currentState, character)
        return self.terminal_state == currentState

    def __str__(self):
        automata = "Initial state: %s\nTerminal state: %s\n" % (self.initial_state.id, self.terminal_state.id)"
        for state in self.states:
            automata += str(state) + "\n"
        return automata
# We are going to define a deterministic finite automaton that accepts only binary numbers that are multiples of 3. 
if __name__ == '__main__':
    s0 = State("s0")
    s1 = State("s1")
    s2 = State("s2")

    s0.add_link('0', s0)
    s0.add_link('1', s1)
    s1.add_link('0', s2)
    s1.add_link('1', s0)
    s2.add_link('0', s1)
    s2.add_link('1', s2)

    a = Automata(s0, [s0, s1, s2], s0)
    print(a)
    print("1011101 is " + ("accepted." if a.accepts('1011101') else "rejected.")) 
    print("10111011 is " + ("accepted." if a.accepts('10111011') else "rejected."))

Initial state: s0 Terminal state: s0 (s0): 0 : s0 1 : s1  
(s1): 0 : s2 1 : s0  
(s2): 0 : s1 1 : s2  
1011101 is accepted. 10111011 is rejected.

class State:
    def __init__(self, id):
        self.id = id
        self.links = []

    def add_link(self, symbol, newState):
        self.links.append( (symbol, newState) )

    def __eq__(self, otherState):
        if otherState==None: return False
        return self.id == otherState.id
    
    def __str__(self):
        state = "(%s):\n" % self.id
        for (symbol, newState) in self.links:
            state += str(symbol) + " : " + str(newState.id) + "\n"
        return state

class Automata:
    def __init__(self, initial_state, states, terminal_state):
        self.initial_state = initial_state
        self.states = states
        self.terminal_state = terminal_state

    def get_next_state(self, current_state, character):
        # get_next_state will return None if the current state is None or the current character from the input has no transition from the current state. 
        if current_state==None or len(current_state.links)==0: 
            return None

        for (symbol, newState) in current_state.links:
            if symbol == character:
                return newState
        return None
    
    def accepts(self, string):
        currentState = self.initial_state
        for character in string:
            currentState = self.get_next_state(currentState, character)
            if currentState==None: # This is the only difference with the previous code!!! 
                return False
                
        return self.terminal_state == currentState

    def __str__(self):
        automata = "Initial state: %s\nTerminal state: %s\n" % (self.initial_state.id, self.terminal_state.id)
        for state in self.states:
            automata += str(state) + "\n"
        return automata
    
# We are going to define a deterministic finite automaton that accepts or recognizes the regular expression: ba*b
if __name__ == '__main__':
    s0 = State("s0")
    s1 = State("s1")
    s2 = State("s2")

    s0.add_link('b', s1)
    s1.add_link('a', s1)
    s1.add_link('b', s2)
    
    a = Automata(s0, [s0, s1, s2], s2)
    print(a)
    print("baab is " + ("accepted" if a.accepts('baab') else "rejected")) 
    print("abaaba is " + ("accepted" if a.accepts('abaaba') else "rejected"))
    print("cbaaba is " + ("accepted" if a.accepts('abaaba') else "rejected"))
    print("baaba is " + ("accepted" if a.accepts('abaaba') else "rejected"))

Initial state: s0 Terminal state: s2 (s0): b : s1
(s1): a : s1 b : s2
(s2):
baab is accepted, abaaba is rejected, cbaaba is rejected, baaba is rejected

Bitcoin donation

JustToThePoint Copyright © 2011 - 2022 Anawim. ALL RIGHTS RESERVED. Bilingual e-books, articles, and videos to help your child and your entire family succeed, develop a healthy lifestyle, and have a lot of fun.

This website uses cookies to improve your navigation experience.
By continuing, you are consenting to our use of cookies, in accordance with our Cookies Policy and Website Terms and Conditions of use.