Let $G$ be a finite state automaton (FSA) with transfer function $\delta(\cdot,\cdot)$ and initial state $q_0$. Suppose also $\Sigma_{G}$ represents its alphabet. Assume that its closed behavior is a set of strings defined as:

$L(G) := \{s \in \Sigma_{G}|\delta(q_0,s) \text{ is defined in }G\}$

Now, consider two particular FSA $G_1$ and $G_2$ such that $\Sigma_{G_{1}} \subseteq \Sigma_{G_{2}}$. Clearly, then we clearly have $\Sigma_{G_{1}}^{*} \subseteq \Sigma_{G_{2}}^{*}$. I'm wondering whether or not we necessarily conclude that $L(G_{1}) \subseteq L(G_{2})$.

To me, it's not always true. Am I right?

Here is a simple example to contradict it:

enter image description here

in which $\Sigma_{G_{1}}^{*} \subseteq \Sigma_{G_{2}}^{*}$, but $L(G_{1}) \supseteq L(G_{2})$.

  • 1
    $\begingroup$ This sounds like a silly exercise. If you don't know anything about the connection between $G_1,G_2$, there is no reason to expect any connected between $L(G_1),L(G_2)$. Perhaps you have misread the question? $\endgroup$ – Yuval Filmus Nov 24 '17 at 13:34
  • $\begingroup$ @YuvalFilmus: Well, I don't think it's a silly exercise since this issue is raised in the case of a research problem about supervisory control of discrete-event systems. As well, as I noted in the question, I have a contrapositive example, and just wanted to make sure there is no fallacy in the resulting conclusion. $\endgroup$ – Roboticist Nov 24 '17 at 18:55

Your claim implies that $L(G)$ depends only on the alphabet of $G$, but this is clearly false. So the claim itself must be false.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.