How to implement epsilon transition?

Question

I am currently trying to implement CYK with epsilon transition. How does the algorithm provided handles epsilon transitions? If not how would you go about to implement it? (I am using Java)

Answer 1

The answer you are looking for is here What it says is that any epsilon transition can be represented into fewer simple transitions. An epsilon transition is ambiguous. To cover this ambiguity computationally you need to generate all possible outcomes from a given transition.

Example 1:

A -> aA | e

is

A-> a
A-> aA

Example 2:

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

is

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

where e stands for ε (epsilon) transition

You can see that you have to generate all possible outcomes out of the epsilon transition in order to cover the ambiguity. I think it is fascinating how an ambiguity can be expressed computationally.

Source for example 2 here