Skip to content

Issue of Transition Table in EX 3.7.3 (4)? #228

@porsche-zheng

Description

@porsche-zheng

Issur Position

url

In exercise 3.7.3 (4), current NAF and Transition Table is:

NFA

3 7 3-4-nfa

Transition table

NFA State DFA State a b
{0,1,2,4,7} A B C
{1,2,3,4,6,7,8} B B D
{1,2,4,5,6,7} C B C
{1,2,4,5,6,7,9} D B E
{1,2,4,5,6,7,10,11,12,14,17} E F G
{1,2,3,4,6,7,8,11,12,13,14,16,17} F F H
{1,2,4,5,6,7,11,12,13,15,16,17} G F G
{1,2,4,5,6,7,9,11,12,14,15,16,17} H F I
{1,2,4,5,6,7,10,11,12,14,15,16,17} I F G

Core Issue

Focusing on DFA state G, 13 is belongs to corresponding NFA state. But I think it should be 14.

Because $G=\epsilon_closure(5)\cup\epsilon_closure(15)$, we can not reach 13. But we can transfer 14 via $\epsilon$.

Note

That's only my opinion and may be wrong. Thanks for reviewing.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions