0
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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