# NFA Extended Transition Function Input Processing

##### Question: $\sum = \{ 0,1 \} \\ \\ L = \{ w|w \text{ over} \sum^* \text{ where w has 1 before the ending symbol} \}$

Equivalent regular expression: $(0 + 1)^* 1 (0 + 1)$

#### The NFA:

Here, $N = (Q, \sum, \delta, q_0, F) = ( \{q_0,q_1,q_2 \} , \{ 0,1 \} , \delta , q_0 , \{ q_2 \} )$

#### Transition Function: $\delta (q_0, 0 ) = \{ q_0 \} \\ \\ \delta (q_0, 1 ) = \{ q_0, q_1 \} \\ \\ \delta (q_1, 0 ) = \{ q_2 \} \\ \\ \delta (q_1, 1 ) = \{ q_2 \} \\ \\ \delta (q_2, 0 ) = \emptyset \\ \\ \delta (q_2, 1 ) = \emptyset \\$

#### Input Processing Shown with Arrows:

###### For input string, w = 011 $\hat{\delta} (q_0, \epsilon ) = \{ q_0 \} \\ \\ \\ \hat{\delta} (q_0, 0 ) = \{ q_0 \} \\ \\ \\ \hat{\delta} (q_0, 01 ) = \delta ( \hat{\delta} (q_0, 0 ), 1 ) \\ ............. = \delta ( q_0, 1 ) \\ ............. = \{ q_0, q_1 \} \\ \\ \\ \hat{\delta} (q_0, 011 ) = \delta ( \hat{\delta} (q_0, 01 ), 1 ) \\ .............. = \delta ( \{ q_0, q_1 \}, 1 ) \\ .............. = \delta ( q_0, 1 ) \cup \delta ( q_1, 1 ) \\ .............. = \{ q_0, q_1 \} \cup \{ q_2 \} \\ .............. = \{ q_0, q_1, q_2 \} \\$ $\hat{\delta} (q_0, 010 ) = \delta ( \hat{\delta} (q_0, 01 ), 0 ) \\ .............. = \delta ( \{ q_0, q_1 \}, 0 ) \\ .............. = \delta ( q_0, 0 ) \cup \delta ( q_1, 0 ) \\ .............. = \{ q_0 \} \cup \{ q_2 \} \\ .............. = \{ q_0, q_2 \} \\ \\ \\ \hat{\delta} (q_0, 0101 ) = \delta ( \hat{\delta} (q_0, 010 ), 1 ) \\ ................. = \delta ( \{ q_0, q_2 \}, 1 ) \\ ................. = \delta ( q_0, 1 ) \cup \delta ( q_2, 1 ) \\ ................. = \{ q_0, q_1 \} \cup \emptyset \\ ................. = \{ q_0, q_1 \} \\ \\ \\ \hat{\delta} (q_0, 01010 ) = \delta ( \hat{\delta} (q_0, 0101 ), 0 ) \\ .................. = \delta ( \{ q_0, q_1 \}, 0 ) \\ .................. = \delta ( q_0, 0 ) \cup \delta ( q_1, 0 ) \\ .................. = \{ q_0 \} \cup \{ q_2 \} \\ .................. = \{ q_0, q_2 \} \\$