NFA в DFA, где государство имеет только эпсилон-переход

Question

Если при преобразовании таблицы NFA в таблицу DFA существует состояние, которое только в виде эпсилон-перехода, то как оно преобразуется в таблицу DFA.

Например, если состояние 1 принимает только 2 в столбце ε, как оно будет выглядеть в преобразовании DFA?

Таблица переходов:

     a     b     c    ε
1   {}    {}    {}   {2}
2   {3}   {}    {}   {}
3   {4}   {3,4} {}   {}
4   {4}   {}    {}   {}

Answer 1

Я думаю, что лучше сначала исключить эпсилон-переход, чтобы получить NFA (без эпсилон-перехода).От NFA должно быть проще получить эквивалентный DFA.

Как устранить эпсилон-переход?

Во-первых, у нас есть термин ECLOSE состояния.ECLOSE(q) определяется как набор всех состояний (включая само состояние q), которые могут быть достигнуты после перехода в эпсилон.В вашем случае:

ECLOSE(1) = {1,2}

Чтобы исключить эпсилон-переход, выполните следующие шаги:

1. Если ECLOSE(1) содержит конечное состояние, тогда установите state 1 в качестве конечного состояния
2. Добавить переход (с соответствующей меткой) из state 1 в state q тогда и только тогда, когда есть переход из некоторых состояний в ECLOSE(1) в state q
3. Теперь вы можете удалить все эпсилонпереходы.

После описанных выше шагов (вы не указали, какие состояния являются начальными и / или конечными), вы должны получить:

    a     b     c    
1   {3}   {}    {}   
2   {3}   {}    {}   
3   {4}   {3,4} {}   
4   {4}   {}    {}