0
$\begingroup$

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.

$\endgroup$

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.