6
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\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, 2018 at 9:31
  • $\begingroup$ Thanks for the reply but I still don't see why :( $\endgroup$
    – John
    Sep 14, 2018 at 9:41
  • $\begingroup$ Do you see multiple finite controls of automaton in the same state at any point? $\endgroup$
    – Deep Joshi
    Sep 14, 2018 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, 2018 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, 2018 at 10:13

2 Answers 2

Reset to default
5
$\begingroup$

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.

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

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

Improve this answer
$\endgroup$
0

Your Answer

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

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