Pedagogical Puzzles

So often we find that ``trivial exercises'' and ``obvious remarks'' prove tough nuts to crack. We introduce a column devoted to some seemingly innocuous problems which people have encountered in the course of their work.

\newcommand{\abs}[1]{|{#1}|}
\newcommand{\To}{\rightarrow}
\newcommand{\Sin}{s_{in}}
\newcommand{\Step}[1]{\stackrel{{#1}}{\longrightarrow}}

We begin with an exercise from B\"uchi's posthumously published textbook on automata theory (Finite Automata, Their Algebras and Grammars: Towards a Theory of Formal Expressions, D.~Siefkes (Ed.), Springer-Verlag, New York (1989)). This contribution is from Kamal Lodaya, IMSc, Madras.

Let $A = (S,\To,\Sin,F)$ be a deterministic finite automaton (DFA) over an alphabet $\Sigma$, where, as usual, $S$ is the set of states, $\Sin \in S$ is the initial state, $\To$ is the transition function from $S \times \Sigma$ to $S$ and $F$ is the set of final states.
If we assume that $\To$ is total, we can associate with each word $w \in \Sigma^*$, a function $\delta_w: S \to S$ where $\delta_w(s) = s'$ iff $s \Step{w}^* s'$. This function is well-defined since $\To$ is deterministic and total.
Suppose that $\abs{S} = n$. It is not difficult to show the following: For every word $w$, there is a word $u$ such that $\abs{u} < n^n$ and the functions $\delta_w$ and $\delta_u$ coincide.
The puzzle is the following: Show that the $n^n$ bound can be improved to $n!$. In other words, for every word $w$, there is a word $u$ such that $\abs{u} < n!$ and $\delta_w = \delta_u$.
The other part of the puzzle is to show that this bound is tight: For every $n$ state automaton over a three-letter alphabet, find a word $w$ such that $\abs{w} = n! - 1$ and $\delta_w \neq \delta_u$ if $\abs{u} < n! - 1$.

Our second puzzle comes from K~Narayan Kumar, SPIC Math Inst, Madras.

Let $A$ be a DFA with $n$ states over an alphabet $\Sigma$ such that $A$ accepts all strings of length less than or equal to $n$. It is not difficult to show that the language accepted by $A$ must in fact be $\Sigma^*$.
The question is whether the same fact holds when $A$ is an NFA---in other words, if $A$ is an NFA with $n$ states such that $A$ accepts all strings of length less than or equal to $n$, is it necessarily the case that $A$ accepts {\em all\/} strings in $\Sigma^*$?

Send in your solutions to us. The best ones will be published in the next Newsletter. (At the moment, we don't have an answer for either problem!)

We also welcome contributions to this column---remember that the aim is to publicize problems which ``should be easy'' but are not.