patternMinor
Find the language an NFA recognizes
Viewed 0 times
thenfalanguagerecognizesfind
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#97311, answer score: 5
Revisions (0)
No revisions yet.