(c) C rules, except that an underscore cannot be followed by a digit.
6. Find a grammar for a certain type of scientific notation for real numbers on
which the following rules hold:
(a) The number can be preceded by a + or − sign, or the sign may be absent.
(b) Numeric values must be of the form a.b 1 b 2 …b n , where b i is any digit,
but a must be a nonzero digit.
(c) The number may be followed by an exponent field of the form e + yy or
e − yy, where y can be any digit.
7. In the Roman number system, numbers are represented by strings on the
alphabet {M,D, C, L, X, V, I}. Design an accepter that accepts such strings
only if they are properly formed Roman numbers. For simplicity, replace the
“subtraction” convention in which the number nine is represented by IX with
an addition equivalent that uses VIIII instead.
8. We assumed that an automaton works in a framework of discrete time steps,
but this aspect has little influence on our subsequent discussion. In digital
design, however, the time element assumes considerable significance.
In order to synchronize signals arriving from different parts of the
computer, delay circuitry is needed. A unit-delay transducer is one that
simply reproduces the input (viewed as a continual stream of symbols) one
time unit later. Specifically, if the transducer reads as input a symbol a at
time t, it will reproduce that symbol as output at time t + 1. At time t = 0,
the transducer outputs nothing. We indicate this by saying that the
transducer translates input a 1 a 2 … into output λa 1 a 2 ….
Draw a graph showing how such a unit-delay transducer might be
designed for ∑ = {a, b}.
9. An n-unit delay transducer is one that reproduces the input n time units later;
that is, the input a 1 a 2 …is translated into λ n a 1 a 2 …, meaning again that the
transducer produces no output for the first n time slots.
(a) Construct a two-unit delay transducer on ∑ = {a, b}.
(b) Show that an n-unit delay transducer must have at least |∑| n states.
6. Find a grammar for a certain type of scientific notation for real numbers on
which the following rules hold:
(a) The number can be preceded by a + or − sign, or the sign may be absent.
(b) Numeric values must be of the form a.b 1 b 2 …b n , where b i is any digit,
but a must be a nonzero digit.
(c) The number may be followed by an exponent field of the form e + yy or
e − yy, where y can be any digit.
7. In the Roman number system, numbers are represented by strings on the
alphabet {M,D, C, L, X, V, I}. Design an accepter that accepts such strings
only if they are properly formed Roman numbers. For simplicity, replace the
“subtraction” convention in which the number nine is represented by IX with
an addition equivalent that uses VIIII instead.
8. We assumed that an automaton works in a framework of discrete time steps,
but this aspect has little influence on our subsequent discussion. In digital
design, however, the time element assumes considerable significance.
In order to synchronize signals arriving from different parts of the
computer, delay circuitry is needed. A unit-delay transducer is one that
simply reproduces the input (viewed as a continual stream of symbols) one
time unit later. Specifically, if the transducer reads as input a symbol a at
time t, it will reproduce that symbol as output at time t + 1. At time t = 0,
the transducer outputs nothing. We indicate this by saying that the
transducer translates input a 1 a 2 … into output λa 1 a 2 ….
Draw a graph showing how such a unit-delay transducer might be
designed for ∑ = {a, b}.
9. An n-unit delay transducer is one that reproduces the input n time units later;
that is, the input a 1 a 2 …is translated into λ n a 1 a 2 …, meaning again that the
transducer produces no output for the first n time slots.
(a) Construct a two-unit delay transducer on ∑ = {a, b}.
(b) Show that an n-unit delay transducer must have at least |∑| n states.