Quiz 01 (January, 30th)

Statistics

There were 3 problems, each worth 10 points.

Problem 1

Give the state transition diagram of a DFA that recognizes those binary strings that begin and end with a different digit.

Solution

Problem 2

Give a regular expression for the set of binary strings in (1)

Solution

The following regular expression generates the set of binary strings from (1):

  (0(0 u 1)*1) u (1(0 u 1)*1)

Problem 3

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?

Solution

A string w = w_1w_2...w_n is accepted by an NFA = (Q,\Sigma,\delta,q_0,F) if there exists a sequence (p_0,...,p_m) of states in Q and a representation y = y_1y_2...y_m of w over \Sigma_\epsilon such that:

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.


February, 1st