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

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
```

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

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

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

**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:

**Q is a finite set of states**. In the first example (Fig. A.1), there are three states: S0, S1, and S2. They are represented graphically by circles.**Σ is the alphabet**. It is a finite set of input symbols. The previous automaton takes a string of 0s and 1s as input.**δ is a transition function, δ : Q × Σ → Q**meaning that the automaton moves into the state δ(q, a) if it receives the input symbol “a” while in state “q”. For example, if the automaton is currently in state S1 and the current input symbol is 0, then the automaton moves or jumps into the state S2.- q0 is an
**initial or start state**. Obviously, q0∈Q. - F is a
**set of accepting states**, F⊆Q. These are used to accept or reject sequences of inputs given to the automaton and they are depicted by two double circles.

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).
```

**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.
```

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')
```

```
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')
```

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