Конечные автоматы в Python: теория и практическое применение

class StateMachine:
def __init__(self):
# Определение состояний
self.states = {'start', 'found_a', 'found_b', 'accepted'}
# Текущее состояние
self.current_state = 'start'
# Принимающие состояния
self.accepting_states = {'accepted'}
# Функция переходов как словарь: {текущее_состояние: {символ: новое_состояние}}
self.transitions = {
'start': {'a': 'found_a', 'b': 'found_b'},
'found_a': {'a': 'found_a', 'b': 'accepted'},
'found_b': {'a': 'accepted', 'b': 'found_b'},
'accepted': {'a': 'found_a', 'b': 'found_b'}
}

def process_input(self, input_string):
self.current_state = 'start'

for symbol in input_string:
if symbol not in ('a', 'b'):
return False # Символ не из алфавита

# Получаем новое состояние из функции переходов
if symbol in self.transitions[self.current_state]:
self.current_state = self.transitions[self.current_state][symbol]
else:
return False # Нет перехода для этого символа

# Проверяем, находимся ли мы в принимающем состоянии
return self.current_state in self.accepting_states

# Использование автомата
fsm = StateMachine()
test_strings = ["ab", "ba", "aab", "abb", "c", "abba", ""]

for string in test_strings:
result = fsm.process_input(string)
print(f"Строка '{string}' {'принята' if result else 'отклонена'}")

class State:
def __init__(self, name, is_accepting=False):
self.name = name
self.is_accepting = is_accepting
self.transitions = {} # символ -> новое состояние

def add_transition(self, symbol, state):
self.transitions[symbol] = state

def next_state(self, symbol):
return self.transitions.get(symbol)

class FSM:
def __init__(self, initial_state):
self.initial_state = initial_state
self.current_state = initial_state

def reset(self):
self.current_state = self.initial_state

def process_input(self, input_string):
self.reset()

for symbol in input_string:
next_state = self.current_state.next_state(symbol)
if next_state is None:
return False
self.current_state = next_state

return self.current_state.is_accepting

# Создание автомата
q0 = State("start")
q1 = State("found_a")
q2 = State("found_b")
q3 = State("accepted", is_accepting=True)

# Настройка переходов
q0.add_transition('a', q1)
q0.add_transition('b', q2)
q1.add_transition('a', q1)
q1.add_transition('b', q3)
q2.add_transition('a', q3)
q2.add_transition('b', q2)
q3.add_transition('a', q1)
q3.add_transition('b', q2)

# Создание экземпляра автомата
fsm = FSM(q0)

# Тестирование
test_strings = ["ab", "ba", "aab", "abb", "c", "abba", ""]
for string in test_strings:
if 'c' in string: # Обработка символов вне алфавита
print(f"Строка '{string}' отклонена (символ вне алфавита)")
else:
result = fsm.process_input(string)
print(f"Строка '{string}' {'принята' if result else 'отклонена'}")

class DFA:
def __init__(self):
# Состояния: 0 – начальное, 1 – видели 0, 2 – принимающее (видели 01)
self.states = {0, 1, 2}
self.initial_state = 0
self.accepting_states = {2}

# Функция переходов: словарь {состояние: {символ: новое_состояние}}
self.transitions = {
0: {'0': 1, '1': 0},
1: {'0': 1, '1': 2},
2: {'0': 1, '1': 0}
}

def process(self, input_string):
current_state = self.initial_state

for symbol in input_string:
if symbol not in ('0', '1'):
return False # Символ не из алфавита

current_state = self.transitions[current_state][symbol]

return current_state in self.accepting_states

# Тестирование DFA
dfa = DFA()
test_strings = ["01", "101", "1101", "10", "00", "1", "0", ""]
for string in test_strings:
result = dfa.process(string)
print(f"DFA: Строка '{string}' {'принята' if result else 'отклонена'}")

class NFA:
def __init__(self):
# Состояния: 0 – начальное, 1 – видели 0, 2 – принимающее (видели 01)
self.states = {0, 1, 2}
self.initial_state = 0
self.accepting_states = {2}

# Функция переходов: словарь {состояние: {символ: множество новых состояний}}
self.transitions = {
0: {'0': {0, 1}, '1': {0}, 'ε': set()},
1: {'0': set(), '1': {2}, 'ε': set()},
2: {'0': set(), '1': set(), 'ε': set()}
}

def epsilon_closure(self, states):
"""Находит все состояния, достижимые по ε-переходам из states."""
result = set(states)
stack = list(states)

while stack:
state = stack.pop()
for next_state in self.transitions[state]['ε']:
if next_state not in result:
result.add(next_state)
stack.append(next_state)

return result

def move(self, states, symbol):
"""Находит все состояния, достижимые по переходам с symbol из states."""
result = set()

for state in states:
result.update(self.transitions[state].get(symbol, set()))

return result

def process(self, input_string):
current_states = self.epsilon_closure({self.initial_state})

for symbol in input_string:
if symbol not in ('0', '1'):
return False # Символ не из алфавита

# Переход по текущему символу
current_states = self.move(current_states, symbol)
# Применение ε-замыкания
current_states = self.epsilon_closure(current_states)

if not current_states: # Если нет доступных переходов
return False

# Проверка, есть ли принимающее состояние среди текущих
return any(state in self.accepting_states for state in current_states)

# Тестирование NFA
nfa = NFA()
for string in test_strings:
result = nfa.process(string)
print(f"NFA: Строка '{string}' {'принята' if result else 'отклонена'}")

from pysimpleautomata.automata import Automaton
from pysimpleautomata.DFA import DFA
from pysimpleautomata.NFA import NFA

# Создание DFA через библиотеку
states = {'q0', 'q1', 'q2'}
alphabet = {'0', '1'}
initial_state = 'q0'
accepting_states = {'q2'}
transitions = {
('q0', '0'): 'q1',
('q0', '1'): 'q0',
('q1', '0'): 'q1',
('q1', '1'): 'q2',
('q2', '0'): 'q1',
('q2', '1'): 'q0'
}

dfa_automaton = DFA(states, alphabet, transitions, initial_state, accepting_states)

# Визуализация DFA (требует Graphviz)
# pysimpleautomata.draw.DFA_draw(dfa_automaton, "my_dfa")

class Token:
def __init__(self, type, value):
self.type = type
self.value = value

def __repr__(self):
return f"Token({self.type}, {repr(self.value)})"

class Tokenizer:
def __init__(self):
# Определение состояний
self.START = 'START'
self.INTEGER = 'INTEGER'
self.OPERATOR = 'OPERATOR'
self.PARENTHESIS = 'PARENTHESIS'
self.WHITESPACE = 'WHITESPACE'
self.ERROR = 'ERROR'

# Начальное состояние
self.state = self.START

# Буфер для текущего токена
self.current_buffer = ""

def tokenize(self, text):
self.state = self.START
self.current_buffer = ""
tokens = []

for char in text:
# Обработка переходов на основе текущего состояния и символа
if self.state == self.START:
if char.isdigit():
self.state = self.INTEGER
self.current_buffer = char
elif char in "+-*/":
tokens.append(Token('OPERATOR', char))
elif char in "()":
tokens.append(Token('PARENTHESIS', char))
elif char.isspace():
pass # Игнорируем пробелы в начальном состоянии
else:
self.state = self.ERROR
self.current_buffer = char

elif self.state == self.INTEGER:
if char.isdigit():
self.current_buffer += char
else:
# Добавляем накопленное число в токены
tokens.append(Token('INTEGER', int(self.current_buffer)))
self.current_buffer = ""

# Обрабатываем текущий символ
if char in "+-*/":
tokens.append(Token('OPERATOR', char))
self.state = self.START
elif char in "()":
tokens.append(Token('PARENTHESIS', char))
self.state = self.START
elif char.isspace():
self.state = self.START
else:
self.state = self.ERROR
self.current_buffer = char

elif self.state == self.ERROR:
# В случае ошибки просто пропускаем все символы
# до пробела или оператора
if char.isspace() or char in "+-*/()":
tokens.append(Token('ERROR', self.current_buffer))
self.current_buffer = ""
self.state = self.START

# Обрабатываем текущий символ
if char in "+-*/":
tokens.append(Token('OPERATOR', char))
elif char in "()":
tokens.append(Token('PARENTHESIS', char))
else:
self.current_buffer += char

# Обрабатываем оставшийся буфер
if self.state == self.INTEGER and self.current_buffer:
tokens.append(Token('INTEGER', int(self.current_buffer)))
elif self.state == self.ERROR and self.current_buffer:
tokens.append(Token('ERROR', self.current_buffer))

return tokens

# Тестирование токенизатора
tokenizer = Tokenizer()
expressions = [
"2 + 3 * 4",
"(15 – 5) / 2",
"42 + abc", # С ошибкой
"3 * (7 – 2) + 1"
]

for expr in expressions:
tokens = tokenizer.tokenize(expr)
print(f"Выражение: {expr}")
print(f"Токены: {tokens}")
print()

from pyparsing import Word, nums, alphas, alphanums, Group, Suppress, Forward, Optional, OneOrMore, ZeroOrMore

# Определение простого языка для парсинга JSON-подобной структуры
def create_json_parser():
# Базовые элементы
integer = Word(nums).setParseAction(lambda t: int(t[0]))
string = Suppress('"') + Word(alphanums + " ,.!?-_") + Suppress('"')

# Рекурсивное определение объекта
json_object = Forward()

# Определение пары ключ-значение
key = string.copy()
value = integer | string | json_object
key_value = Group(key + Suppress(':') + value)

# Объект – это набор пар ключ-значение в фигурных скобках
json_object << (Suppress('{') + 
Optional(key_value + ZeroOrMore(Suppress(',') + key_value)) + 
Suppress('}'))

return json_object

# Тестирование парсера
json_parser = create_json_parser()
test_json = '{"name": "John", "age": 30, "address": {"city": "New York", "zip": 10001}}'

try:
result = json_parser.parseString(test_json)
print("Результат парсинга:")
print(result.dump())
except Exception as e:
print(f"Ошибка парсинга: {e}")

def is_valid_email(email):
# Состояния автомата
START = 0
IN_LOCAL = 1
AFTER_AT = 2
IN_DOMAIN = 3
IN_TLD = 4
ERROR = 5

state = START

for char in email:
if state == START:
if char.isalnum() or char in '_-.':
state = IN_LOCAL
else:
state = ERROR
break

elif state == IN_LOCAL:
if char == '@':
state = AFTER_AT
elif not (char.isalnum() or char in '_-.'):
state = ERROR
break

elif state == AFTER_AT:
if char.isalnum():
state = IN_DOMAIN
else:
state = ERROR
break

elif state == IN_DOMAIN:
if char == '.':
state = IN_TLD
elif not char.isalnum():
state = ERROR
break

elif state == IN_TLD:
if char == '.':
continue # Разрешаем несколько точек в домене
elif not char.isalnum():
state = ERROR
break

# Проверка финального состояния
return state == IN_TLD

# Тестирование валидатора email
test_emails = [
"user@example.com",
"user.name@company.co.uk",
"user_name@domain-example.org",
"invalid@",
"@domain.com",
"user@.com"
]

for email in test_emails:
valid = is_valid_email(email)
print(f"Email '{email}' {'валиден' if valid else 'невалиден'}")

def minimize_dfa(states, alphabet, transitions, initial_state, accepting_states):
"""
Алгоритм минимизации DFA через поиск эквивалентных состояний.
Упрощённая реализация алгоритма Хопкрофта.
"""
# Начальное разделение: принимающие и непринимающие состояния
partitions = [accepting_states, states – accepting_states]

# Удаляем пустые разделы
partitions = [p for p in partitions if p]

changed = True
while changed:
changed = False
new_partitions = []

for partition in partitions:
# Словарь для группировки состояний по их переходам
subgroups = {}

for state in partition:
# Создаём подпись состояния на основе его переходов
signature = []

for symbol in sorted(alphabet):
if (state, symbol) in transitions:
next_state = transitions[(state, symbol)]

# Находим индекс раздела, содержащего next_state
for i, p in enumerate(partitions):
if next_state in p:
signature.append((symbol, i))
break
else:
signature.append((symbol, None))

# Преобразуем подпись в неизменяемый тип для использования в качестве ключа
signature = tuple(signature)

if signature not in subgroups:
subgroups[signature] = set()
subgroups[signature].add(state)

# Если раздел был разбит
if len(subgroups) > 1:
changed = True
new_partitions.extend(subgroups.values())
else:
new_partitions.append(partition)

partitions = new_partitions

# Создание минимизированного DFA
new_states = set()
new_transitions = {}
new_accepting_states = set()

# Маппинг старых состояний на новые
state_mapping = {}

for i, partition in enumerate(partitions):
new_state = f"q{i}"
new_states.add(new_state)

for old_state in partition:
state_mapping[old_state] = new_state

if old_state in accepting_states:
new_accepting_states.add(new_state)

# Обновление переходов
for (old_state, symbol), next_state in transitions.items():
if old_state in state_mapping and next_state in state_mapping:
new_transitions[(state_mapping[old_state], symbol)] = state_mapping[next_state]

# Определение нового начального состояния
new_initial_state = state_mapping[initial_state]

return new_states, new_transitions, new_initial_state, new_accepting_states

# Пример использования
states = {'q0', 'q1', 'q2', 'q3', 'q4'}
alphabet = {'0', '1'}
transitions = {
('q0', '0'): 'q1', ('q0', '1'): 'q2',
('q1', '0'): 'q1', ('q1', '1'): 'q3',
('q2', '0'): 'q4', ('q2', '1'): 'q2',
('q3', '0'): 'q1', ('q3', '1'): 'q3',
('q4', '0'): 'q4', ('q4', '1'): 'q2',
}
initial_state = 'q0'
accepting_states = {'q3', 'q4'}

min_states, min_transitions, min_initial, min_accepting = minimize_dfa(
states, alphabet, transitions, initial_state, accepting_states
)

print("Минимизированный DFA:")
print(f"Состояния: {min_states}")
print(f"Переходы: {min_transitions}")
print(f"Начальное состояние: {min_initial}")
print(f"Принимающие состояния: {min_accepting}")

class State:
def handle(self, context, event):
pass

class Context:
def __init__(self, state):
self.state = state

def transition_to(self, state):
self.state = state

def handle_event(self, event):
self.state.handle(self, event)

# Пример составного/иерархического состояния
class CompositeState(State):
def __init__(self):
self.sub_states = {}
self.current_sub_state = None
self.entry_state = None

def add_sub_state(self, name, state, is_entry=False):
self.sub_states[name] = state
if is_entry or self.entry_state is None:
self.entry_state = name

def enter(self):
"""Вызывается при входе в составное состояние"""
self.current_sub_state = self.entry_state

def handle(self, context, event):
if self.current_sub_state:
# Делегирование обработки текущему подсостоянию
sub_state = self.sub_states[self.current_sub_state]
sub_state.handle(self, event)
else:
# Обработка на уровне составного состояния
pass

# Пример использования для игрового AI
class IdleState(State):
def handle(self, context, event):
if event == "ENEMY_SPOTTED":
context.transition_to(CombatState())
print("Переход из Idle в Combat")

class PatrolState(State):
def handle(self, context, event):
if event == "COMPLETED_PATROL":
context.transition_to(IdleState())
print("Переход из Patrol в Idle")
elif event == "ENEMY_SPOTTED":
context.transition_to(CombatState())
print("Переход из Patrol в Combat")

class CombatState(CompositeState):
def __init__(self):
super().__init__()
self.add_sub_state("ATTACK", AttackState(), is_entry=True)
self.add_sub_state("DEFEND", DefendState())

def handle(self, context, event):
if event == "ENEMY_FLED":
context.transition_to(PatrolState())
print("Переход из Combat в Patrol")
else:
super().handle(context, event)

class AttackState(State):
def handle(self, context, event):
if event == "LOW_HEALTH":
context.current_sub_state = "DEFEND"
print("Переход из Attack в Defend")

class DefendState(State):
def handle(self, context, event):
if event == "HEALTH_RESTORED":
context.current_sub_state = "ATTACK"
print("Переход из Defend в Attack")

# Демонстрация работы
ai_context = Context(IdleState())
ai_context.handle_event("ENEMY_SPOTTED") # Idle -> Combat (Attack)
ai_context.handle_event("LOW_HEALTH") # Combat:Attack -> Combat:Defend
ai_context.handle_event("HEALTH_RESTORED") # Combat:Defend -> Combat:Attack
ai_context.handle_event("ENEMY_FLED") # Combat -> Patrol

from transitions import Machine

class PlayerModel:
def __init__(self):
self.health = 100
self.ammo = 30

# Обратные вызовы
self.on_enter_combat = lambda: print("Вход в боевой режим!")
self.on_exit_combat = lambda: print("Выход из боевого режима")

def has_ammo(self):
return self.ammo > 0

def is_alive(self):
return self.health > 0

def reload(self):
self.ammo = 30
print("Перезарядка завершена")

def take_damage(self, amount):
self.health -= amount
print(f"Получен урон: {amount}. Оставшееся здоровье: {self.health}")

def fire(self):
if self.ammo > 0:
self.ammo -= 1
print(f"Выстрел! Осталось патронов: {self.ammo}")
return True
return False

# Определение состояний и переходов
states = ['idle', 'combat', 'reload', 'dead']

# Создание экземпляра модели
player = PlayerModel()

# Создание машины состояний
machine = Machine(
model=player, 
states=states, 
initial='idle'
)

# Добавление переходов
machine.add_transition(
trigger='spot_enemy', 
source='idle', 
dest='combat',
conditions=['is_alive', 'has_ammo']
)

machine.add_transition(
trigger='spot_enemy', 
source='idle', 
dest='reload',
conditions=['is_alive'],
unless=['has_ammo']
)

machine.add_transition(
trigger='no_ammo', 
source='combat', 
dest='reload',
conditions=['is_alive']
)

machine.add_transition(
trigger='reload_complete', 
source='reload', 
dest='idle'
)

machine.add_transition(
trigger='enemy_gone', 
source='combat', 
dest='idle'
)

machine.add_transition(
trigger='killed', 
source='*', # Из любого состояния
dest='dead',
conditions=['is_alive']
)

# Симуляция поведения
print(f"Текущее состояние: {player.state}")
player.spot_enemy()
print(f"Текущее состояние: {player.state}")

# Стреляем, пока есть патроны
while player.state == 'combat' and player.has_ammo():
player.fire()

print(f"Текущее состояние: {player.state}")

# Перезаряжаемся и возвращаемся в исходное состояние
if player.state == 'reload':
player.reload()
player.reload_complete()

print(f"Текущее состояние: {player.state}")

# Получаем смертельный урон
player.take_damage(120)
player.killed()
print(f"Текущее состояние: {player.state}")

import sqlite3

class PersistentFSM:
def __init__(self, db_path, machine_id):
self.db_path = db_path
self.machine_id = machine_id
self._setup_db()
self._load_state()

def _setup_db(self):
conn = sqlite3.connect(self.db_path)
cursor = conn.cursor()

# Создаём таблицу для хранения состояний, если её нет
cursor.execute('''
CREATE TABLE IF NOT EXISTS fsm_states (
machine_id TEXT PRIMARY KEY,
current_state TEXT,
data TEXT
)
''')

conn.commit()
conn.close()

def _load_state(self):
conn = sqlite3.connect(self.db_path)
cursor = conn.cursor()

cursor.execute(
"SELECT current_state, data FROM fsm_states WHERE machine_id = ?", 
(self.machine_id,)
)

row = cursor.fetchone()

if row:
self.current_state, self.data = row[0], row[1]
else:
# По умолчанию
self.current_state = 'START'
self.data = ''
cursor.execute(
"INSERT INTO fsm_states VALUES (?, ?, ?)",
(self.machine_id, self.current_state, self.data)
)

conn.commit()
conn.close()

def save_state(self):
conn = sqlite3.connect(self.db_path)
cursor = conn.cursor()

cursor.execute(
"UPDATE fsm_states SET current_state = ?, data = ? WHERE machine_id = ?",
(self.current_state, self.data, self.machine_id)
)

conn.commit()
conn.close()

def transition(self, new_state, data=None):
self.current_state = new_state
if data is not None:
self.data = data
self.save_state()

def get_state(self):
return self.current_state, self.data

# Пример использования
fsm = PersistentFSM('fsm_database.db', 'order_processing')
current_state, data = fsm.get_state()
print(f"Текущее состояние: {current_state}, данные: {data}")

# Переход в новое состояние
fsm.transition('PROCESSING', 'order_id=12345')
current_state, data = fsm.get_state()
print(f"Новое состояние: {current_state}, данные: {data}")