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

NFA A_n

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?

  • Try to trace the automaton with n = 2 and input string 11111. You might get something that why that edge doesn't matter. – Deep Joshi Sep 14 at 9:31
  • Thanks for the reply but I still don't see why :( – John Sep 14 at 9:41
  • Do you see multiple finite controls of automaton in the same state at any point? – Deep Joshi Sep 14 at 9:53
  • 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. – John Sep 14 at 10:09
  • 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. – John Sep 14 at 10:13
up vote 5 down vote accepted

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.

  • Yes, because $\{0,1\}^{*}$ can overlap/cover/equally replace all prefixes a string when it uses the "go back to start" edge. – RandomPerfectHashFunction Sep 14 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}$.

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

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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