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:

NFA accepting w 1 alphabet
NFA accepting w 1 alphabet

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


Transition Table:

NFA transition table
NFA transition table

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
nfa input tracing 011
nfa input tracing 011

For input string, w = 01010
nfa 01010
nfa 01010

Extended transition Function Input Processing:

For input, 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 \} \\


For input, w = 01010. Since sub-string 01 is already calculated I will reuse it.

\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 \} \\

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s