Реализация оптимизации конечного автомата, представленного функциями перехода на Python

August 19, 2018 19:02

Как мы уже успели узнать, конечный автомат - это абстрактная модель, которая содержит в себе конечное число состояний чего-либо. Он используется для управления потоком или выполнения каких-либо команд. Конечный автомат хорошо подойдет для использования в играх, например в качестве искусственного интеллекта, таким образом будет получено удобное решение с минимальным количеством кода.

Конечный автомат - это модель вычислений, основанная на гипотетической машине состояний. Это значит, что в какой-то момент времени будет активно только одно состояние. Это в свою очередь значит, что для выпонения действий машина должна менять состояние.

#!/bin/python
# Пример реализации оптимизации конечного автомата, представленного функциями перехода

import string
from threading import Thread

from igraph import Graph, plot
from texttable import Texttable


def parse_f(f):
    left, right = list(map(lambda x: x.strip(), f.split('=')))
    state, symbol = list(map(lambda x: x.strip('f() '), left.split(',')))

    return state, symbol, right


def draw_plot(q, f, h, z):
    edges = [(q.index(v[0]), q.index(v[2])) for v in f]
    edges_attrs = [v[1] for v in f]

    graph = Graph(vertex_attrs={"label": q},
                  edges=edges,
                  edge_attrs={"label": edges_attrs},
                  directed=True)

    graph.vs['color'] = ['gray' if v in z else (lambda v: 'lightblue' if v in h else 'white')(v) for v in q]

    plot(graph,
         **{'vertex_size': 40},
         bbox=(480, 320),
         margin=50,
         layout=graph.layout_kamada_kawai())


def achievable_vertices(h, f, cur=None, q=set(), count=0):
    if count < len(f):
        if cur is None:
            cur = h[0]
            q.add(cur)

        cur = [item[2] for item in f if item[0] == cur]

        if len(cur) > 1:
            for i in cur:
                q.add(i)

                achievable_vertices(h, f, i, q, count + 1)

        elif len(cur) == 1:
            cur = cur[0]
            q.add(cur)

            achievable_vertices(h, f, cur, q, count + 1)
    return list(q)


def print_table(q, parsed_F):
    T = list(set([v[1] for v in parsed_F]))

    table = Texttable()
    table.header([' '] + q)

    for t in T:
        row = [t] + [(set([v[2] if v[1] == t else '-' for v in parsed_F if v[0] == _q])) for _q in q]
        row = list(map(lambda x: ''.join(x) if len(x) == 1 else ''.join(x).strip('-'), row))
        table.add_row(row)
    print(table.draw())


def del_eq(q, f):

    terminals = list(set([v[1] for v in f]))
    new_symbols = list(set(string.ascii_uppercase) - set(q) - set('F'))

    for terminal in terminals:
        row = [(item[0], item[2]) for item in f if item[1] == terminal]

        for i in [item[1] for item in row]:
            duplicate = [item for item in row if item[1] == i]
            if len(duplicate) > 1:

                d = set([item[0] for item in duplicate])
                q = list(set(q) - d)
                new_symbol = new_symbols.pop()
                q.append(new_symbol)

                for i, p in enumerate(f):
                    if p[0] in list(d):
                        f[i] = new_symbol, p[1], p[2]
                    if p[2] in list(d):
                        f[i] = p[0], p[1], new_symbol

                f = list(set(f))
                return del_eq(q, f)
    return q, f


def lab_04():
    Q = list('KLQTSMRUNOPF')
    F = ['f(K, 1) = M', 'f(L, 0) = K', 'f(Q, 0) = R', 'f(T, 1) = Q', 'f(T, ]) = U',
         'f(S, [) = M', 'f(M, 0) = R', 'f(M, 1) = R', 'f(R, ]) = U', 'f(R, &) = L',
         'f(R, ~) = O', 'f(N, 1) = M', 'f(O, 0) = N', 'f(P, 1) = R', 'f(F, 0) = P', 'f(F, ]) = U']
    Z = list('U')
    H = list('S')

    f = [parse_f(f) for f in F]

    Thread(target=lambda: draw_plot(Q, f, H, Z)).start()
    print_table(Q, f)

    Q = achievable_vertices(H, f)  # поиск достижимых вершин
    F = [f for f in F if parse_f(f)[0] in Q]  # фильтрация переходов
    f = [parse_f(f) for f in F]

    Thread(target=lambda: draw_plot(Q, f, H, Z)).start()
    print_table(Q, f)

    Q, f = del_eq(Q, f)

    Thread(target=lambda: draw_plot(Q, f, H, Z)).start()
    print_table(Q, f)

lab_04()