I am working through a chapter of a book by Samuel Eilenberg about Automata, Languages and Machines as part of an university course in computer science.

And as an exercise in this chapter I have to show the statement above. I have to use two propositions that were shown in the book earlier.

Let $A$ be a subset of $\Sigma^*$ then the cardinality of this family of sets: $ \{\ s^{-1}A\ \vert \ s \in \Sigma^*\} $ is called $ \alpha ^{e}A$.

$\ s^{-1}A = \{x \ \vert \ sx \in A \} $

With $\varnothing$ deleted the cardinality of the family of sets is called $\alpha A$.

Any subset $A$ of $\Sigma^*$ is recognizable iff this family of sets is finite.

The first proposition is the following:

Let $A$ be a recognizable subset of $\Sigma^*$, and let $\mathfrak A = (Q, i, T)$ be a deterministic (resp. complete) $\Sigma$-Automaton such that $\vert \mathfrak A \vert = A$ (Meaning that $\mathfrak A$ recognizes $A$.), then $card \ Q \ge \alpha A$ (resp. $card \ Q \ge \alpha ^{e}A $). With equality holding if and only if $\mathfrak A$ is minimal (resp. complete minimal).

The second proposition is the following:

If $f\colon \ \Sigma^* \to \Gamma^*$ is a morphism and $B$ is a recognizable subset of $\Gamma^*$, then $A = Bf^{-1}$ is a recognizable subset of $\Sigma^*$ and $\alpha A \le \alpha B$.

I think the first proposition explains it for $ C = A \cup B$ and $ D = A \cap B$ since $\alpha C \le \alpha A + \alpha B$ and $\alpha D \le \alpha A$ or $\alpha D \le \alpha B$.

For $E = \Sigma^* - A$ I dont understand how to show that it's true. I guess I have to use the second proposition because so far I didn't need it. Anyway somehow I have to derive bounds for $\alpha E$ to show that it is recognizable.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.