Holooly Plus Logo
Holooly Plus Logo

Question 1.50: Read the informal definition of the finite state transducer ...

Read the informal definition of the finite state transducer given in Exercise 1.24. Prove that no FST can output w^{R} for every input w if the input and output alph-abets are {0,1}.

The blue check mark means that this solution has been answered and checked by an expert. This guarantees that the final answer is accurate.
Learn more on how we answer questions.

Assume to the contrary that some FST T outputs w^{R} on input w. Consider the input strings 00 and 01. On input 00, T must output 00, and on input 01, T must output 10. In both cases, the first input bit is a 0 but the first output bits differ. Operating in this way is impossible for an FST because it produces its first output bit before it reads its second input. Hence no such FST can exist.

Related Answered Questions

Question: 1.7

Give state diagrams of NFAs with the specified number of states recognizing each of the following languages. In all parts, the alphabet is {0,1}. a. The language {w| w ends with 00} with three states f. The language 1^* (011^+)^* with three states ...

Verified Answer:

Question: 1.55

The pumping lemma says that every regular language has a pumping length p, such that every string in the language can be pumped if it has length p or more. If p is a pumping length for language A, so is any length p^′ ≥ p. The minimum pumping length for A is the smallest p that is a pumping length ...

Verified Answer:

(a) The minimum pumping length is 4. The string 00...
Question: 1.52

Myhill–Nerode theorem. Refer to Problem 1.51. Let L be a language and let X be a set of strings. Say that X is pairwise distinguishable by L if every two distinct strings in X are distinguishable by L. Define the index of L to be the maximum number of elements in any set that is pairwise ...

Verified Answer:

(a) We prove this assertion by contradiction. Let ...
Question: 1.44

Let B and C be languages over Σ= {0, 1}. Define ...

Verified Answer:

Let M_{B} = (Q_{B},\Sigma , \delta _{B},q_{...
Question: 1.46

Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection, and complement. b. {0^m 1^n| m≠n} ...

Verified Answer:

(b) Let B= \left\{0^{m}1^{n} \mid m\neq n \...
Question: 1.40

Recall that string x is a prefix of string y if a string z exists where xz = y, and that x is a proper prefix of y if in addition x ≠ y. In each of the following parts, we define an operation on a language A. Show that the class of regular languages is closed under that operation. ...

Verified Answer:

(a) Let M = (Q, \Sigma ,\delta ,q_{0} ,F)[/...
Question: 1.29

Use the pumping lemma to show that the following languages are not regular. a. A1= {0^n 1^n 2^n |n≥0 } c. A3 = {a^2^n| n ≥0 } (Here, a^2^n means a string of 2^n a’s. ) ...

Verified Answer:

(a) Assume that A_{1} = \left\{0^{n}1^{n}2^...
Question: 1.23

Let B be any language over the alphabet Σ. Prove that B = B^+ iff BB ⊆ B. ...

Verified Answer:

We prove both directions of the “iff.” (→) Assume ...
Question: 1.11

Prove that every NFA can be converted to an equivalent one that has a single accept state. ...

Verified Answer:

Let  N = (Q,\Sigma ,\delta ,q_{0}, F )[/lat...
Question: 1.5

Each of the following languages is the complement of a simpler language. In each part, construct a DFA for the simpler language, then use it to give the state diagram of a DFA for the language given. In all parts, ∑= {a, b}. ...

Verified Answer:

(a) The left-hand DFA recognizes {ω| ω contains ab...