1
$\begingroup$

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})$.

$\endgroup$
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$ Commented Nov 24, 2017 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$
    – user33772
    Commented Nov 24, 2017 at 18:55

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.