Недетерминированные конечные автоматы {ab, abc}* в Python

Я пытался нарисовать этот недетерминированный конечный автомат:

NFA с количеством состояний не более 3 для языка {ab, abc}*, и я пришел к решению на картинке ниже:

Диаграмма NFA

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

print("Insert below the string: ")
string = str(input())


def state_q0(string):
    if len(string) == 0:
        print("string not accepted")
    else:
        if string[0] == "a":
            state_q1(string[1:])
        elif string[0] == "b":
            print("rejected")


def state_q1(string):
    if len(string) == 0:
        print("string not accepted")
    else:
        if string[1] == "b":
            state_q2(string[2:])
        else:
            print("rejected")


def state_q2(string):
    if len(string) == 0:
        print("string not accepted")
    else:
        if string[2] == "c":
            print("accepted -> q0")
        elif string[2] == "b":
            print("rejected")


state_q0(string)

python-3.x python dfa nfa
person Flavio Andrade    schedule 17.02.2021    source источник
comment
Не могли бы вы добавить пример того, что вы ожидаете в качестве результата с учетом конкретного ввода?   -  person rhurwitz    schedule 17.02.2021

Ответы (1)


arrow_upward
2
arrow_downward

Вы всегда должны смотреть на первый символ строки и вызывать рекурсивные вызовы, используя все, кроме первого символа.

Также это не отмечено на вашей диаграмме, но я предполагаю, что q0 является принимающим состоянием, поскольку оно соответствует (ab + abc)*.

Итак, в вашем стиле (который я бы лично не использовал, но хорошо):

def q0(s):
    if not s: return "accept"  # Accepting state.
    if s[0] == "a": return q1(s[1:])
    return "reject"

def q1(s):
    if not s: return "reject"
    # NFA, must try both edges.
    if (s[0] == "b" and q0(s[1:]) == "accept" or
        s[0] == "b" and q2(s[1:]) == "accept"):
        return "accept"
    return "reject"

def q2(s):
    if not s: return "reject"
    if s[0] == "c": return q0(s[1:])
    return "reject"

Однако, как бы я кодировал NFA, он выглядит так:

transitions = [
    {"a": {1}},
    {"b": {0, 2}},
    {"c": {0}}
]
starting_state = 0
accepting_states = {0}

def nfa(w):
    cur_states = {starting_state}
    for c in w:
        if not cur_states: return "reject"
        cur_states = set.union(*
            (transitions[s].get(c, set()) for s in cur_states))
    return "accept" if cur_states & accepting_states else "reject"
person orlp    schedule 17.02.2021
comment
Спасибо за объяснение. Я возьму некоторое время на изучение кода и реализацию, а затем вернусь. - person Flavio Andrade; 17.02.2021