# Find the language an NFA recognizes

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?

• 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 '18 at 9:31
• Thanks for the reply but I still don't see why :( – John Sep 14 '18 at 9:41
• Do you see multiple finite controls of automaton in the same state at any point? – Deep Joshi Sep 14 '18 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 '18 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 '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.

• 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 '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}$.

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