Chapter 14

(a) If a computer is being designed to operate with a character set of 350 symbols, how many bits must be reserved for each character? Assume each character will use the same number of bits. (b) Do the same for 3,500 symbols.

Draw the transition dingrams for the machines of the following monoids: (a) \(\left[Z_{4} ;+_{4}\right]\) (b) The direct product of \(\left[\mathrm{Z}_{2} ; \mathrm{x}_{2}\right]\) with itself.

For each of the subsets of the indicated monoid, determine whether the subset is a submonoid. (a) \(S_{1}=\\{0,2,4,6\\}\) and \(S_{2}=\\{1,3,5,7\\}\) in \(\left[\mathbb{Z}_{8} ; \times_{8}\right]\) (b) \(\left\\{f \in \mathbb{N}^{\mathbb{N}}: f(n) \leqslant n, \forall n \in \mathbb{N}\right\\}\) and \(\left\\{f \in \mathbb{N}^{\mathbb{N}}: f(1)=2\right\\}\) in the monoid \(\left[\mathbb{N}^{\mathbb{N}} ; \circ\right]\) (c) \(\\{A \subseteq \mathbb{Z} \mid A\) is finite \(\\}\) and \(\left\\{A \subseteq \mathbb{Z} \mid A^{c}\right.\) is finite \(\\}\) in \([\mathcal{P}(\mathbb{Z}) ; \cup]\).

For each subset, describe the submonoid that it generates. (a) \(\\{3\\}\) in \(\left[\mathbb{Z}_{12} ; \times_{12}\right]\) (b) \(\\{5\\}\) in \(\left[\mathbb{Z}_{25} ; \times_{25}\right]\) (c) the set of prime numbers in \([\mathbb{P} ; \cdot]\) (d) \(\\{3,5\\}\) in \([\mathbb{N} ;+]\)

Can two finite-state machines with nonisomorphic transition diagrams have isomorphic monoids?

An \(n \times n\) matrix of real numbers is called stochastic if and only if each entry is nonnegative and the sum of entries in each column is 1\. Prove that the set of stochastic matrices is a monoid over matrix multiplication.

What sets of strings are defined by the following grammar? (a) Terminal symbols: \(\lambda, a, b,\) and \(c\) (b) Nonterminal symbols: \(S, T, U\) and \(E\) (c) Starting symbol: \(S\) (d) Production rules: $$ \begin{array}{ccc} S \rightarrow a S & S \rightarrow T & T \rightarrow b T \\ T \rightarrow U & U \rightarrow c U & U \rightarrow E \\ & E \rightarrow \lambda & \end{array} $$

What input sequence would be used to compute the sum of 1101 and 0111 (binary integers)? What would the output sequence be?

A semigroup is an algebraic system \([S ; *]\) with the only axiom that \(*\) be associative on \(S\). Prove that if \(S\) is a finite set, then there must exist an idempotent element, that is, an \(a \in S\) such that \(a * a=a\).

Let \(B\) be a Boolean algebra and \(M\) the set of all Boolean functions on \(B\). Let \(*\) be defined on \(M\) by \((f * g)(a)=f(a) \wedge g(a) .\) Prove that \([M ; *]\) is a monoid. Construct the operation table of \([M ; *]\) for the case of \(B=B_{2}\).

Define the following languages over \(B\) with phrase structure grammars. Which of these languages are regular? (a) The strings with more 0's than 1's. (b) The strings with an even number of 1 's. (c) The strings for which all 0's precede all 1 's.

Prove that if a language over \(A\) is recursive, then its complement is also recursive.

(a) Prove that if \(X_{1}, X_{2}, \ldots\) is a countable sequence of countable sets, the union of these sets, \(\bigcup_{i=1}^{\infty} X_{i}\) is countable. (b) Using the fact that the countable union of countable sets is countable, prove that if \(A\) is countable, then \(A^{*}\) is countable.