1
$\begingroup$

enter image description here

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 ?

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Chaman Agrawal Jun 25 '18 at 18:15
  • $\begingroup$ Right, in that case the NFA accepts the language $1(0+1)(0+1)$. $\endgroup$ – Yuval Filmus Jun 25 '18 at 18:35

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.