Let us consider nondeterministic finite automata with -transitions (-NFAs) over the alphabet .
An -NFA is an NFA that can additionally have "silent" transitions labeled with a fresh symbol .
A word is accepted by an -NFA if there exists a word such that:
is accepted by (when is considered an NFA over the alphabet ); and
removing all the occurrences of in gives rise to .
The language of an -NFA is the set of words accepted by .
An example of an -NFA is given below; it is referred to as . Here is an initial state and is an accepting state.
Answer the following questions:
(1) Give a regular expression that designates the language of the above -NFA .
(2) Give an NFA over such that: ; and is -free, that is, there are no transitions labeled with \varepsilon in .
(3) Give an -NFA such that
Your answer may be -free.
(4) Give an -NFA such that , where is from Question (3). Your answer may be -free.
(5) Give an -NFA such that , where is from Question (3). Your answer may be -free.
