The following regular expression generates the set of binary strings from (1):
(0(0 u 1)*1) u (1(0 u 1)*1)
Complete the following formal statement of what it means for a string w1...wn to be accepted by a nondeterministic finite automaton:
A string w = w1w2...wn is accepted by an NFA = (Q,\Sigma,d,q0,F) if there exists a sequence (p0,...,pm) of states in Q and a representation y = y1y2...ym of w over \Sigma_\epsilon such that ...
In the above statement, what is meant by a "representation" of w?
where y = y_1y_2...y_m is a string over the alphabet \Sigma_\epsilon such that m >= n, and if we remove all \epsilon symbols from y then we obtain the string w. That is, y is w with epsilon symbols inserted between certain symbols.
Comment: We insert the epsilon symbols so we do not have to handle epsilon transitions in the NFA in any special way.