3. Each case has a straightforward solution.
13. Enumerate all cases with |v| = 2 to get
16. (c) You just have to get each symbol once. The term
will do this, but is not enough since the a will precede the b, etc. For the
complete solution you must generate all permutations of the three
symbols, giving six terms that can be added. The answer, although quite
long, is conceptually not hard.
17. (c) Create two 0’s, interspersed with 1’s, then repeat. But don't forget the
case when there are no 0’s at all. Solution: (1 * 01 * 01 * ) * + 1 * .
18. (a) Create all strings of length three and repeat. A short solution is ((a + b +
c)(a + b + c)(a + b + c)) * .
20. (c) The statement
is true. By the given rules (r 1 + r 2 ) * denotes the language (L (r 1 ) ∪ L (r 2 )) * ,
that is, the set of all strings of arbitrary concatenations of elements of L (r 1 )
and L (r 2 ). But (r 1
* r 2
* ) * denotes ((L(r 1 )) * (L(r 2 )) * ) * , which is the same set.
23. The expression for an infinite language must involve at least one starred
subexpression, otherwise it can only denote finite strings. If there is one
starred subexpression that denotes a non-empty string, then this string can
be repeated as often as desired and therefore denote arbitrarily long strings.
25. A closed contour will be generated by an expression r if and only if n i (r)=
n r (r) and n u (r) = n d (r).
27. Notice several things. The bit string must be at least 6 bits long. If it is
longer than 6 bits, its value is at least 64, so anything will do. If it is exactly
6 bits, then either the second bit from the left (16) or the third bit from the
13. Enumerate all cases with |v| = 2 to get
16. (c) You just have to get each symbol once. The term
will do this, but is not enough since the a will precede the b, etc. For the
complete solution you must generate all permutations of the three
symbols, giving six terms that can be added. The answer, although quite
long, is conceptually not hard.
17. (c) Create two 0’s, interspersed with 1’s, then repeat. But don't forget the
case when there are no 0’s at all. Solution: (1 * 01 * 01 * ) * + 1 * .
18. (a) Create all strings of length three and repeat. A short solution is ((a + b +
c)(a + b + c)(a + b + c)) * .
20. (c) The statement
is true. By the given rules (r 1 + r 2 ) * denotes the language (L (r 1 ) ∪ L (r 2 )) * ,
that is, the set of all strings of arbitrary concatenations of elements of L (r 1 )
and L (r 2 ). But (r 1
* r 2
* ) * denotes ((L(r 1 )) * (L(r 2 )) * ) * , which is the same set.
23. The expression for an infinite language must involve at least one starred
subexpression, otherwise it can only denote finite strings. If there is one
starred subexpression that denotes a non-empty string, then this string can
be repeated as often as desired and therefore denote arbitrarily long strings.
25. A closed contour will be generated by an expression r if and only if n i (r)=
n r (r) and n u (r) = n d (r).
27. Notice several things. The bit string must be at least 6 bits long. If it is
longer than 6 bits, its value is at least 64, so anything will do. If it is exactly
6 bits, then either the second bit from the left (16) or the third bit from the