EXERCISES
EXERCISES
3.1 Modify the DIGDEC machine shown in Figure 3.3 so that it
accepts a string over the alphabet X ={d, ∗}. For example, strings
such as s = 324 ∗ 41 ∗ 9 ∗ 199 ∗∗230∗ are valid inputs. An
asterisk causes the machine to execute the OUT(num) function
where num denotes the decimal number corresponding to the
digits received prior to the current asterisk but after any previous
asterisk. Thus, the output of the machine for input string s will be:
OUT(324) OUT(41) OUT(9) OUT(199) OUT(230)
Note that the machine does not perform any action if it receives
an asterisk following another asterisk.
3.2 Show that (a) V-equivalence and equivalence of states and
machines as defined in Section 3.2.3 are equivalence relations,
that is they obey the refle ...