754
Modeling Arithmetic, Computation, and Languages
25. a. set of all strings containing an even number of 0s
b. set of all strings consisting of two or more 1s followed by a 0
c. set of all strings containing two consecutive 0s and the rest 1s
26. a. set of all strings ending with one or more 0s
b. set of all strings where the number of 0s is a multiple of 3
c. set of all strings containing at least four 1s
27. a. set of all strings containing exactly one 1
b. set of all strings beginning with 000
c. set of all strings where the second input is 0 and the fourth input is 1
28. a. set of all strings consisting entirely of any number (including none) of 01 pairs or consisting entirely of
two 1s followed by any number (including none) of 0s
b. set of all strings ending in 110
c. set of all strings containing 00
29. A paragraph of English text is to be scanned and the number of words beginning with “con” counted.
Design a finite-state machine that will output a 1 each time such a word is encountered. The output alphabet is 50, 16. The input alphabet is the 26 letters of the English alphabet, a finite number of punctuation
symbols (period, comma, and so on), and a special character b for blank. To simplify your description,
you may use I − 5m6, for example, to denote any input symbol not equal to m.
30. a. In many computer languages, any decimal number N must be presented in one of the following forms:
sd*
sd*.d*
d*
d*.d*
(1)
where s denotes the sign (s [ 5+, − 6), d is a digit (d [ 50, 1, 2, … , 96), and d* denotes a string of
digits where the string may be of any length, including length zero (the empty string). Thus, the following would be examples of valid decimal numbers:
+2.74
−.58
129
+
Design a finite-state machine that recognizes valid decimal numbers by producing an output of 1. The
input symbols are +, −, . , and the 10 digits. To simplify notation, you may use d to denote any digit
input symbol.
b. Modify the machine of part (a) to recognize any sequence of decimal numbers as defined in part (a)
separated by commas. For example, such a machine would recognize
+2.74,−.58,129,+
The input alphabet should be the same as for the machine of part (a) with the addition of the symbol c
for comma.
c. Suppose a decimal number must be presented in a form similar to that for part (a) except that any decimal point that appears must have at least one digit before it and after it. Write an expression similar to
expression (1) in part (a) to describe the valid form for a decimal number. How would you modify the
machine of part (a) to recognize such a number?
31. Let M be a finite-state machine with n states. The input alphabet is 506. Show that for any input sequence
that is long enough, the output of M must eventually be periodic. What is the maximum number of inputs
before periodic output begins? What is the maximum length of a period?
Modeling Arithmetic, Computation, and Languages
25. a. set of all strings containing an even number of 0s
b. set of all strings consisting of two or more 1s followed by a 0
c. set of all strings containing two consecutive 0s and the rest 1s
26. a. set of all strings ending with one or more 0s
b. set of all strings where the number of 0s is a multiple of 3
c. set of all strings containing at least four 1s
27. a. set of all strings containing exactly one 1
b. set of all strings beginning with 000
c. set of all strings where the second input is 0 and the fourth input is 1
28. a. set of all strings consisting entirely of any number (including none) of 01 pairs or consisting entirely of
two 1s followed by any number (including none) of 0s
b. set of all strings ending in 110
c. set of all strings containing 00
29. A paragraph of English text is to be scanned and the number of words beginning with “con” counted.
Design a finite-state machine that will output a 1 each time such a word is encountered. The output alphabet is 50, 16. The input alphabet is the 26 letters of the English alphabet, a finite number of punctuation
symbols (period, comma, and so on), and a special character b for blank. To simplify your description,
you may use I − 5m6, for example, to denote any input symbol not equal to m.
30. a. In many computer languages, any decimal number N must be presented in one of the following forms:
sd*
sd*.d*
d*
d*.d*
(1)
where s denotes the sign (s [ 5+, − 6), d is a digit (d [ 50, 1, 2, … , 96), and d* denotes a string of
digits where the string may be of any length, including length zero (the empty string). Thus, the following would be examples of valid decimal numbers:
+2.74
−.58
129
+
Design a finite-state machine that recognizes valid decimal numbers by producing an output of 1. The
input symbols are +, −, . , and the 10 digits. To simplify notation, you may use d to denote any digit
input symbol.
b. Modify the machine of part (a) to recognize any sequence of decimal numbers as defined in part (a)
separated by commas. For example, such a machine would recognize
+2.74,−.58,129,+
The input alphabet should be the same as for the machine of part (a) with the addition of the symbol c
for comma.
c. Suppose a decimal number must be presented in a form similar to that for part (a) except that any decimal point that appears must have at least one digit before it and after it. Write an expression similar to
expression (1) in part (a) to describe the valid form for a decimal number. How would you modify the
machine of part (a) to recognize such a number?
31. Let M be a finite-state machine with n states. The input alphabet is 506. Show that for any input sequence
that is long enough, the output of M must eventually be periodic. What is the maximum number of inputs
before periodic output begins? What is the maximum length of a period?