📝

1 Add to your calendar

This homework is due for the 2nd of March, 18:15 GMT+1. It should be sent to . Exercises are independent, and can be skipped without penalty. Failure to deliver the homework in due time is heavily penalized.

Exercises without a \(\star\) symbol are mandatory and should be attempted by everyone. Exercises with a \(\star\) symbol are optional and will be rewarded by extra points.

2 Mealy Machines and Variations

2.1 Continuous

Is the zip function continuous? Where zip(w1 # w2) is defined inductively as follows

\[ \begin{aligned} \mathsf{zip}(au \# bv) &= a b \mathsf{zip}(u \# v) \\ \mathsf{zip}(\varepsilon \# v) &= v \\ \mathsf{zip}(u \# \varepsilon) &= u \\ \mathsf{zip}(\varepsilon \# \varepsilon) &= \varepsilon \\ \end{aligned} \]

2.2 Flip-Flop

Show that a flip-flop machine can be obtained by composition of binary flip flop machines. What is the minimal number of intermediate machines needed?

2.3 Decidable

Show that it is decidable whether a rational function is injective. Can you provide an upper bound on the complexity of the decision problem?

Hint: How was decidability of equivalence proven?

Recall that the decidability of equivalence between two rational functions was obtained in the lecture by constructing a language of counterexamples to equivalence and proving that this language was context-free.

2.4 \(\star\) Windowed Transducers

A Mealy machine is called windowed if there exists a constant \(K \in \mathbb{N}\) such that the output of the machine on a given input letter only depends on the letters at distance at most \(K\) from the input letter.

  1. Provide an example of a Mealy Machine that is not windowed.
  2. Is it decidable whether a Mealy Machine is windowed?

The definition of windowed generalizes naturally to unambiguous NFAs with output where every transition is labelled by a single output letter, called unambiguous NFAs with letter-to-letter output.

  1. Is it decidable whether an unambiguous NFA with letter-to-letter output is windowed?

3 Semantic properties

3.1 Semantically Functional

Prove that the two models are equivalent, and provide effective conversions.

  1. unambiguous NFA with output (i.e. rational functions)
  2. NFA with output which are functional (i.e., for every input, there is exactly one output, which might arise from different runs)

3.2 \(\star\) Semantically Size Preserving

Prove that the following two subclasses of rational functions are equivalent and provide effective conversions:

  1. unambiguous NFA with output where every transition is labelled by exactly one output letter.
  2. unambiguous NFA with output where for every input word, the output has the same length as the input.
Hint: Intermediate Computational Model

Consider the following intermediate model of computation where it is furthermore assumed that there exists \(K \in \mathbb{N}\) such that at anytime of the run of \(f\), the difference of lengths between the input read so far and the output is at most \(K\).

Show that the intermediate model is equivalent to the syntactical model.

Hint: Finding the constant K

Show that the following function is well-defined: \(\delta(p,q)\) that associates to each pair of states \(p\) and \(q\) of the transducer the difference of length induced by any run from \(p\) to \(q\).