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

Question

В настоящее время я пытаюсь внедрить CYK с эпсилон-переходом. Как предоставленный алгоритм обрабатывает эпсилон-переходы? Если нет, то как вы собираетесь это осуществить? (Я использую Java)

Answer 1

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

Пример 1:

A -> aA | e

является

A-> a
A-> aA

Пример 2:

B->A b A
A->a | e

является

B -> z | A z | z A | A z A
A -> a

где е обозначает ε (эпсилон) переход

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

Источник для примера 2 здесь