For example, I have an NFA $A_n$ with alphabet $\Sigma = \{0, 1\}$.


The language recognized by this NFA is known to be $\{u1v\ |\ u, v \in \Sigma^*, |v| = n − 1\}$.

I was unable to get the answer on my own. What got me stuck was that there is a $1$ between $s$ and $q_1$, plus the $q_n$ toward $s$. I know without the edge $q_n \rightarrow s$, the answer should be $\{0,1\}^* \cdot 1 \cdot \{0,1\}^{n-1}$, which is exactly the solution our lecturer provides. Why doesn't the "go back to start" edge matter?

  • $\begingroup$ Try to trace the automaton with n = 2 and input string 11111. You might get something that why that edge doesn't matter. $\endgroup$
    – Deep Joshi
    Sep 14 '18 at 9:31
  • $\begingroup$ Thanks for the reply but I still don't see why :( $\endgroup$
    – John
    Sep 14 '18 at 9:41
  • $\begingroup$ Do you see multiple finite controls of automaton in the same state at any point? $\endgroup$
    – Deep Joshi
    Sep 14 '18 at 9:53
  • $\begingroup$ I'm not sure what you meant by "multiple finite controls of automaton" (sorry, English is not my native language). But I do see that with n=2 and input=11111, there are two ways the NFA can be recognized: $s s s s q_1 q_2$ or $s q_1 q_2 s q_1 q_2$. I get it now the $1v$ part in $u1v$ - the suffix of strings in the language doesn't change with/without that extra edge, but I don't understand why there is no restrictions in the $u$ part. $\endgroup$
    – John
    Sep 14 '18 at 10:09
  • $\begingroup$ What else I have observed is that if the input starts with 0, ensuring that the first step is $ss$, then there's only one way the input can be recognized - looping the $ss$ for the entire $u$ part, until there are $n$ letters left. The "go back to start" edge will be ignored in this case. $\endgroup$
    – John
    Sep 14 '18 at 10:13

The "go back to start" edge doesn't matter because of nondeterminism and the fact that you can read any string at all while staying in state $s$. Any string that the automaton accepts has an accepting run that doesn't use the "go back to start" edge.

  • $\begingroup$ Yes, because $\{0,1\}^{*}$ can overlap/cover/equally replace all prefixes a string when it uses the "go back to start" edge. $\endgroup$ Sep 14 '18 at 18:20

Let $r=\{0,1\}^{*}\cdot1\cdot\{0,1\}^{n-1}$, be the RegularExpression representing the path $s$ to $q_n$.

Now including the transition from $q_n$ to $s$, $r$ becomes $R=r\cdot(\{0,1\}\cdot r)^{*}$. In $r$, the starting $\{0,1\}^{*}$ is the superset of $r$'s ending $\{0,1\}^{n-1}$.

That is, $\{0,1\}^{n-1} \in \{0,1\}^{*}, \forall n \ge 1$
$\{0,1\} = \{0,1\}^{2-1} \space \implies \{0,1\} \in \{0,1\}^{*}$.

This means that in $R$, ending of the every $r$ concatenates with $\{0,1\}$ inside the brackets of $R$ to becomes $\{0,1\}^{n}$. Now this overlaps with $\{0,1\}^{*}$ from the start of $r$ to become $\{0,1\}^{*}$. This becomes recursive and eats up the entire regular expression.
$\implies \space R = r \space and \space R=R\cdot(\{0,1\}\cdot R)^{*}$

Hence, $R=\{0,1\}^{*}\cdot 1 \cdot \{0,1\}^{n-1}$.

You can alternatively prove this by expanding and rearranging $R=r\cdot(\{0,1\}\cdot r)^{*}$.


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.