Finding a match in PCP problem, Sipser problem 5.3

pcp.py

#!/usr/bin/env python3

dominoes = [("ab", "abab"), ("b", "a"), ("aba", "b"), ("aa", "a")]

def top_str(state):
    return "".join(t[0] for t in state)

def bottom_str(state):
    return "".join(t[1] for t in state)

def check_state(state):
    """Return True if state is valid, and False if state is invalid (contains a
    top and bottom character that does not match)."""
    top = top_str(state)
    bottom = bottom_str(state)
    min_length = min(len(top), len(bottom))
    return top[:min_length] == bottom[:min_length]

def explore(state, depth):
    for tile in dominoes:
        new_state = state + [tile]
        if not check_state(new_state):
            continue
        if top_str(new_state) == bottom_str(new_state):
            print(new_state)
        if depth >= 0:
            # print("depth", depth, "; state", new_state)
            explore(new_state, depth - 1)

explore([], 10)