# What will happen if input is larger than required in a NFA

This is my first time in the field of TOC so I am not able to provide any self-approach while asking .In the above example what will happen if input string is "1001" or "1111"?The state q4 can be reached with the first 3 inputs only ,so what will happen after that ?

An NFA accepts a string $w$ if it has an accepting computation. An accepting computation is an expression of the form $$q_0 \stackrel{x_1}{\to} q_1 \stackrel{x_2}{\to} q_2 \to \cdots \to \stackrel{x_m}{\to} q_m$$ where:

1. Each $x_i$ is either a single letter or $\epsilon$.
2. $x_1 x_2 \ldots x_m = w$.
3. For every $1 \leq i \leq m$, $q_i \in \delta(q_{i-1}, x_i)$.
4. $q_0$ is the initial state, and $q_m$ is an accepting state.

If there are no accepting computations for $w$, then the NFA doesn't accept $w$.

The string $1001$ has no accepting computation. In contrast, the string $1111$ does have an accepting computation: $$q_1 \stackrel1\to q_1 \stackrel1\to q_2 \stackrel1\to q_3 \stackrel1\to q_4$$ Therefore the NFA does accept $1111$.

Another way to define the language accepted by an NFA is through the possible states function. We define $\delta(q,x)$ to be the set of possible states that the NFA is in when it reads the word $x$. You can define $\delta(q,x)$ inductively. The NFA accepts $x$ if $\delta(q_0,x)$ contains an accepting state, where $q_0$ is the initial state. For example, in the case of $1001$,

1. $\delta(q_1, \epsilon) = \{ q_1 \}$.
2. $\delta(q_1, 1) = \{ q_1, q_2 \}$.
3. $\delta(q_1, 10) = \{ q_1, q_3 \}$.
4. $\delta(q_1, 100) = \{ q_1, q_4 \}$.
5. $\delta(q_1, 1001) = \{ q_1, q_2 \}$.

Since neither $q_1$ nor $q_2$ are accepting states, the NFA doesn't accept $1001$. In contrast, for the word $1111$ we have:

1. $\delta(q_1, \epsilon) = \{ q_1 \}$.
2. $\delta(q_1, 1) = \{ q_1, q_2 \}$.
3. $\delta(q_1, 11) = \{ q_1, q_2, q_3 \}$.
4. $\delta(q_1, 111) = \{ q_1, q_2, q_3, q_4 \}$.
5. $\delta(q_1, 1111) = \{ q_1, q_2, q_3, q_4 \}$.

Since $q_4$ is an accepting state, the NFA accepts $1111$.

• And if transition functions delta(q1,0)=q1 and delta(q1,1)=q1 were not there in the above machine ,then "1111" will not be accepted because there is not transition function delta(q4,1) i.e it does not have any accepting computation. right? – Chaman Agrawal Jun 25 '18 at 18:15
• Right, in that case the NFA accepts the language $1(0+1)(0+1)$. – Yuval Filmus Jun 25 '18 at 18:35