Find possible states in an automaton from a given input sequence

210 Views Asked by At

I have an automaton (specifically a nondeterministic finite automaton, NFA) and I am trying to determine the possible states that the automata could be in, given a specific sequence of input symbols (not necessarily starting at the start state).

For example, consider the following NFA: enter image description here Given the input sequence $(0,1)$ we know we could be at either $q_0$ or $q_3$. If the input sequence is $(0,0,0)$ we could be at any of the states $\{q_0,q_1,q_2\}$.

I'm curious if this problem has been studied in automata theory -- does it have a name?

1

There are 1 best solutions below

0
On

Hint: Construct the corresponding deterministic finite-state automaton (by the powerset construction). Then for each input sequence, the automaton will be in a uniquely determined state after reading the input.

In view of the deterministic automaton, there is a function $f(q_0,w)$, which gives for the (unique) initial state $q_0$ and each sequence $w$ the ending state after reading the input.

Your question actually refers to the powerset construction.