動機
学校の課題で決定性チューリングマシンの設計があったので, それの答え合わせ用にチューリングマシンのシミュレーションを行うためのPythonコードを書きましたので共有します。
何回か動作は確認しましたが保証はできません。
コード
dtm.py
from typing import List, Dict, Tuple
from enum import Enum
class Transition(Enum):
"""
Enum representing the direction of transition in a Turing Machine.
Attributes:
RIGHT (int): Represents a move to the right on the tape.
LEFT (int): Represents a move to the left on the tape.
"""
RIGHT = 1
LEFT = -1
class State:
"""
Class representing a state in a Turing Machine.
Attributes:
name (str): The name of the state.
state_transition (Dict[Any, Tuple[Any, Transition, "State"]): A dictionary representing the state transition function. The keys are the current alphabet on the tape, and the values are a tuple of the next alphabet to write on the tape, the direction to move the tape head, and the next state to transition to.
"""
def __init__(self, name: str):
self.name = name
self.state_transition = {}
def set_transition(self, transitions: Dict[str, Tuple[str, Transition, "State"]]):
self.state_transition = transitions
def add_transition(self, transition: str, to: "State"):
transition = transition.split("/")
key = transition[0]
transition = transition[1].split(",")
next_alphabet = transition[0]
direction = Transition.RIGHT if transition[1] == "R" else Transition.LEFT
next_state = to
self.state_transition[key] = (next_alphabet, direction, next_state)
def add_transitions(self, transitions: List[Tuple[str, "State"]]):
for transition in transitions:
self.add_transition(*transition)
def __repr__(self):
ret = f"State {self.name}:\n"
for key, value in self.state_transition.items():
ret += f"\t{key} / {value[0]}, {value[1]} -> {value[2].name}\n"
return ret
__str__ = __repr__
class Tape(List):
"""
Class representing the tape in a Turing Machine.
Attributes:
head (int): The current position of the tape head.
"""
def __init__(self, tape: List[str], head: int = 0):
super().__init__(tape)
self.head = head
def __repr__(self):
while self.head >= len(self):
self.append(" ")
return f"[{''.join(self[:self.head])}][{self[self.head]}][{''.join(self[self.head+1:])}]..."
__str__ = __repr__
def move(self, state: State) -> State:
"""
Moves the tape head to the next position based on the current state.
Args:
state (State): The current state of the Turing Machine.
Returns:
State: The next state of the Turing Machine after the move.
Raises:
ValueError: If the current alphabet on the tape is not in the state transition table.
ValueError: If the tape head moves to a negative position.
"""
if self.head < 0:
raise ValueError("Tape head moved to negative position")
if self.head >= len(self):
self.append(" ")
if self[self.head] not in state.state_transition:
raise ValueError(f"Invalid alphabet {self[self.head]}, current tape {self}")
next_alphabet, direction, next_state = state.state_transition[self[self.head]]
self[self.head] = next_alphabet
self.head += direction.value
return next_state
class Definite_Turing_Machine:
"""
Represents a Definite Turing Machine (DTM).
Attributes:
state (List[State]): The list of states in the DTM.
initial_state (State): The initial state of the DTM.
final_state (State): The final state of the DTM.
current_state (State): The current state of the DTM.
Raises:
ValueError: If the initial state is not in the state list.
ValueError: If the final state is not in the state list.
"""
def __init__(self, state: List[State], initial_state: State, final_state: State):
self.state = state
self.initial_state = initial_state
self.final_state = final_state
self.current_state = initial_state
if not initial_state in state:
raise ValueError("Initial state not in state list")
if not final_state in state:
raise ValueError("Final state not in state list")
def run(self, tape: Tape, report: bool = False) -> Tuple[List[str], State]:
"""
Runs the Turing Machine on the given tape until it reaches the final state.
Args:
tape (Tape): The tape to run the Turing Machine on.
report (bool, optional): Whether to print the current state and tape after each move. Defaults to True.
Returns:
Tuple[List[str], State]: The final tape and state of the Turing Machine.
Raises:
ValueError: If the Turing Machine does not reach the final state.
"""
while self.current_state != self.final_state:
if report:
print(f"Current state: {self.current_state.name}, Current tape: {tape}")
self.current_state = tape.move(self.current_state) # エラーを吐かれたくないならここでエラー処理.
if report:
print(f"Current state: {self.current_state.name}, Current tape: {tape}")
ret = (tape, self.current_state)
self.current_state = self.initial_state
return tape, self.current_state
def check(self, tape: Tape, report: bool = False) -> bool:
"""
Checks if the Turing Machine reaches the final state when run on the given tape.
Args:
tape (Tape): The tape to run the Turing Machine on.
Returns:
bool: True if the Turing Machine reaches the final state, False otherwise.
"""
state = self.run(tape, report)[1]
return state == self.final_state
@classmethod
def parse(cls, states: Dict[str, str], initial_state: str, final_state: str):
"""
Parses a dictionary of states and transitions into a Definite Turing Machine.
Args:
states (Dict[str, str]): A dictionary where keys are state names and values are transition rules.
Each transition rule is a string of the format "input-output;input-output;...".
initial_state (str): The name of the initial state.
final_state (str): The name of the final state.
Returns:
Definite_Turing_Machine: The parsed Definite Turing Machine.
Raises:
ValueError: If the initial state or final state is not in the states dictionary.
"""
states_ = {name: State(name) for name in states}
for name, transitions in states.items():
transitions = transitions.split(";")
if transitions[-1] == "":
transitions = transitions[:-1]
transitions = [transition.split("-") for transition in transitions]
transitions = [(transition[0], states_[transition[1]]) for transition in transitions]
states_[name].add_transitions(transitions)
return cls(list(states_.values()), states_[initial_state], states_[final_state])
DTM = Definite_Turing_Machine
使い方
上図にあるDTMの状態遷移図は
l = \{\omega \# \omega | \omega \in \{a, b\}^*\}
となるような言語lを認識するものです。
これを例にとると,
if __name__ == "__main__":
dtm = DTM.parse(
{
"s": "a/x,R-sa;b/x,R-sb;#/#,R-yz",
"sa": "a/a,R-sa;b/b,R-sa;#/#,R-sas",
"sas": "y/y,R-sas;a/y,R-s_",
"s_": "a/a,L-s_;b/b,L-s_;y/y,L-s_;#/#,L-s_;x/x,R-s; / ,L-s_",
"sb": "a/a,R-sb;b/b,R-sb;#/#,R-sbs",
"sbs": "y/y,R-sbs;b/y,R-s_",
"yz": "y/y,R-yz; / ,R-q",
"q": " / ,R-q"
}, "s", "q")
dtm.run(Tape(list("#")), report=True)
dtm.run(Tape(list("a#a")), report=True)
dtm.run(Tape(list("ab#ba")), report=True)
のようになります.
DTM.parseは状態名をキーに, 遷移方法を値にとる辞書を第一引数に, 初期状態を第二引数に, 受理状態を第三引数にとる関数です.
遷移方法は
現在のアルファベット/書き換える先のアルファベット,右(R)or左(L)-遷移先の状態名;
のように書いてください
例えば, yz状態からはyのアルファベットを読んだらそれをyに書き換え, 右に一つヘッドを動かし, yzに遷移
また, 空白を読んだら空白に書き換え, ヘッドを一つ右にずらし, qに遷移
という場合には, "y/y,R-yz; / ,R-q"のように書きます.
末尾のセミコロンはあってもなくてもかまいません。
受理状態になったら勝手に止まりますが, 今回示した" / ,R-q"のように, 何かしら書いといてください。
チューリングマシンのシミュレーションにはrunメソッドを用いてください. 第一引数にテープ, 第二引数には途中の状態遷移を報告するかどうかを示すものを入れます. 第二引数は省略すると報告しない状態になります.
テープはTape(list("テープの初期状態"))のように指定してください.
実行例
使い方に示したコードを実行すると下のようになります
$ py dtm.py
Current state: s, Current tape: [][#][]...
Current state: yz, Current tape: [#][ ][]...
Current state: q, Current tape: [# ][ ][]...
Current state: s, Current tape: [][a][#a]...
Current state: sa, Current tape: [x][#][a]...
Current state: sas, Current tape: [x#][a][]...
Current state: s_, Current tape: [x#y][ ][]...
Current state: s_, Current tape: [x#][y][ ]...
Current state: s_, Current tape: [x][#][y ]...
Current state: s_, Current tape: [][x][#y ]...
Current state: s, Current tape: [x][#][y ]...
Current state: yz, Current tape: [x#][y][ ]...
Current state: yz, Current tape: [x#y][ ][]...
Current state: q, Current tape: [x#y ][ ][]...
Current state: s, Current tape: [][a][b#ba]...
Current state: sa, Current tape: [x][b][#ba]...
Current state: sa, Current tape: [xb][#][ba]...
Current state: sas, Current tape: [xb#][b][a]...
Traceback (most recent call last):
File "dtm.py", line 197, in <module>
dtm.run(Tape(list("ab#ba")), report=True)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "dtm.py", line 134, in run
self.current_state = tape.move(self.current_state) # エラーを吐かれたくないならここでエラー処理.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "dtm.py", line 87, in move
raise ValueError(f"Invalid alphabet {self[self.head]}, current tape {self}")
ValueError: Invalid alphabet b, current tape [xb#][b][a]...
テープは[ヘッドより前のテープ][ヘッドの指し示すアルファベット][ヘッドより後のテープ]のように文字列化されます.
状態遷移の指定されていないアルファベットが読み込まれたときはエラーが発生します.
これを避けるには, コードの134行目にコメントで残しておいた部分でValueErrorのエラー処理を行えば可能になると考えられます。