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

gameLife

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()

gameLife

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)

gameLife3

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)

gameLife4

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:

automaton

Fig.A - Automatons.

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’)

automaton2

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 PhD. Máximo Núñez Alarcón, 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.