readme.md

Лабораторна робота з 3го курсу, перевірка двох недетермінованих скінченних автоматів на еквівалентність

Формат автомату в вхідних данних:

• перша лінія: розмір алфавіту
• друга лінія: кількість станів в автоматі
• третя лінія: початковий стан
• четверта лінія: список фінальних станів
• далі список переходів в авотоматі.

Програма читає з stdin два недетерміновах скінченних автомати, конвертує їх в детерміновані, і перевіряє еквівалентність цих автоматів.

Перевірка автоматів робиться подібно до мінімізації автомату(аналогічно будується множина розрізнюванх станів):

1. обєднуємо два автомати в один
2. будуємо множину розрізнюваних станів
3. перевіряємо чи початкові стани автоматів розрізнювані - якщо так автомати не еквівалентні

lab.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from collections import deque

__author__ = 'z_bodya'


def readAutomata():
    A = int(raw_input())
    S = int(raw_input())
    s0 = int(raw_input())
    inp = raw_input().split(' ')

    F = frozenset([int(inp[i + 1]) for i in range(len(inp) - 1)])
    f = []
    while 1:
        try:
            (s1, a, s2) = raw_input().split(' ')
            f.append((int(s1), ord(a) - ord('a'), int(s2)))
        except EOFError:
            break
        except ValueError:
            break
    f = frozenset(f)
    return A, S, s0, F, f


def transformNFAtoDFA(nfa):
    A = range(nfa[0])
    s0 = frozenset([nfa[2]])
    S = set([s0])
    f = set([])
    queue = deque([s0])
    while len(queue):
        current = queue.popleft()
        movements = filter(lambda x: (x[0] in current), nfa[4])
        for symbol in A:
            destination = frozenset([x[2] for x in filter(lambda x: x[1] == symbol, movements)])
            if len(destination) == 0:
                continue
            if destination not in S:
                S.add(destination)
                queue.append(destination)
            f.add((current, symbol, destination))

    states = list(S)
    s0 = states.index(s0)
    S = frozenset(range(len(states)))
    f = frozenset(map(lambda x: (states.index(x[0]), x[1], states.index(x[2])), f))
    F = frozenset([states.index(a) for a in filter(lambda x: len(x.intersection(nfa[3])), states)])

    return len(A), len(S), s0, F, f


def testDFAEq(dfa1, dfa2):
    if dfa1[0] != dfa2[0]:
        return False
    s1 = dfa1[2]
    s2 = dfa2[2] + dfa1[1]
    S = dfa1[1] + dfa2[1]
    A = range(dfa1[0])
    F = frozenset(list(dfa1[3]) + [dfa1[1] + j for j in dfa2[3]])
    f = frozenset(list(dfa1[4]) + map(lambda x: (x[0] + dfa1[1], x[1], x[2] + dfa1[1]), dfa2[4]))
    diff = set([(i, j) for i in set(range(S)) - set(F) for j in F])
    flag = True
    while flag:
        flag = False
        for i in range(S):
            for j in range(i):
                if ((i, j) not in diff) and ((j, i) not in diff):
                    for a in A:
                        k = l = -1
                        for m in filter(lambda x: x[1] == a, f):
                            if m[0] == i:
                                k = m[2]
                            if m[0] == j:
                                l = m[2]
                        if (k < 0) or (l < 0): continue
                        if ((k, l) in diff) or ((l, k) in diff):
                            diff |= set([(i, j)])
                            flag = True
    return ((s1, s2) not in diff) and ((s2, s1) not in diff)


A1 = readAutomata()
A2 = readAutomata()

B1 = transformNFAtoDFA(A1)
B2 = transformNFAtoDFA(A2)

print testDFAEq(B1, B2)

test.txt

2
3
0
1 2
0 a 1
0 b 1
1 a 1
1 b 1
0 a 2
2 a 1
2 b 1
2 a 2

2
4
0
2 3 2
0 a 1
0 b 1
0 a 3
1 a 2
1 b 2
2 a 2
2 b 2
3 a 3
3 b 2