h(x) = \begin{cases}x/2&2\text{ teilt }x\\0&\text{sonst}\end{cases}
a(x) = \begin{cases}\perp&x=1234\vee x=7266281\\x&\text{sonst}\end{cases}
1.
""" <Sprache> ________ __\ /__ |__ TM __| /______\ { True } """
2.
""" <Sprache> ________ __\ /__ |__ TM __| /______\ { True, False } """
#!/usr/bin/env python3 from itertools import product def nth(n: int, l: list): return map(lambda x: x[n-1], l) def first(l: list): return nth(1, l) def second(l: list): return nth(2, l) def concatenation(l: list, idxs: list): l = list(l) return ''.join(map(lambda i: l[i], idxs)) def find_index_lists(pairs: list, search_all=False): length = 0 while True: length += 1 print("Searching for lists of length {}".format(length)) l = find_index_lists_of_length(pairs, length, search_all=search_all) if l and not search_all: return l def find_index_lists_of_length(pairs: list, length: int, search_all=False): for index_list in product(range(0,len(pairs)), repeat=length): concat = concatenation(first(pairs), index_list) if concat == concatenation(second(pairs), index_list): print("Found solution: {} ({})".format(index_list, concat)) if not search_all: return index_list def inspect(pairs: list, idxs: list): one = concatenation(first(pairs), idxs) two = concatenation(second(pairs), idxs) if one == two: print("MATCH! {} → {}".format(idxs, one)) else: print("no match. {} ↓\n{}\n{}".format(idxs, one, two)) def parse_k(s: str): if s[0] == '[' or s[-1] == ']': return list(map(lambda x: tuple(x.split(',')), s[2:-2].split('),('))) elif s[0] == '(' or s[-1] == ')': return tuple(map(lambda x: tuple(x.split(',')), s[2:-2].split('),('))) else: raise ValueError("Invalid element for K: {}".format(s)) """ if __name__ == '__main__': import sys if len(sys.argv) == 1: print("Usage: {} K [TEST_LIST]\n with K being a list like: [(001,0),(01,011),(01,101),(10,001)]\n and TEST_LIST being an index list like: [0, 2, 1, 2]".format(sys.argv[0])) else: args = sys.argv[1:] args[0] = parse_k(args[0]) if len(args) == 2: index_list = tuple(map(lambda s: int(s), args[1][1:-1].split(','))) inspect(args[0], index_list) else: find_index_lists(*args) """
find_index_lists([('1', '101'), ('10', '00'), ('011', '11')])
ausführen
inspect([('001', '0'), ('01', '011'), ('01', '101'), ('10', '001')], (1, 3, 2, 3, 3, 1, 0, 1, 3, 2, 3, 2, 3, 3, 2, 3, 3, 1, 0, 3, 3, 1, 0, 2, 3, 0, 0, 2, 3, 3, 3, 1, 0, 1, 0, 0, 0, 2, 3, 2, 3, 0, 1, 0, 3, 3, 1, 0, 3, 0, 0, 2, 3, 0, 0, 2, 0, 0, 2, 0, 1, 0, 3, 0, 0, 2))
