Q$2$

$3$ Points

Grading comment:

We now take

N

$1$

N

$1$

$$

above, and add one more

$\backslash$epsi

$\backslash$epsi transition to it$,$ to obtain a new NFA. We consider two ways to do this, as follows.

Let

N

$3$

N

$3$

$$

to be the same as

N

$1$

N

$1$

$$

above, except with one additional transition

$\backslash$delta

$($

q

$0$

$,$

$\backslash$epsi

$)$

$=$

$\{$

q

$1$

$\}$

$\backslash$delta $($q

$0$

$$

$,\backslash$epsi $)=\{$q

$1$

$$

$\}$

Let

N

$4$

N

$4$

$$

be the same as

N

$1$

N

$1$

$$

above, except with one additional transition

$\backslash$delta

$($

q

$0$

$,$

$\backslash$epsi

$)$

$=$

$\{$

q

$2$

$\}$

$\backslash$delta $($q

$0$

$$

$,\backslash$epsi $)=\{$q

$2$

$$

$\}$

Which of the resulting languages

L

$($

N

$3$

$)$

$,$

L

$($

N

$4$

$)$

L$($N

$3$

$$

$),$L$($N

$4$

$$

$)$ is the same as the original language

L

$($

N

$1$

$)$

L$($N

$1$

$$

$)?$

The following multiple$-$choice options contain math elements, so you may need to read them in your screen reader's $$reading$$ or $$browse$$ mode instead of $$forms$$ or $$focus$$ mode.

Choice $1$ of $4$: Both, namely

L

$($

N

$1$

$)$

$=$

L

$($

N

$3$

$)$

$=$

L

$($

N

$4$

$)$

L$($N

$1$

$$

$)=$L$($N

$3$

$$

$)=$L$($N

$4$

$$

$)$

Choice $2$ of $4$: Only

N

$3$

N

$3$

$$

$,$ namely

L

$($

N

$1$

$)$

$=$

L

$($

N

$3$

$)$

$!=$

L

$($

N

$4$

$)$

L$($N

$1$

$$

$)=$L$($N

$3$

$$

$)$

$$

$$

$=$L$($N

$4$

$$

$)$

Choice $3$ of $4$: Only

N

$4$

N

$4$

$$

$,$ namely

L

$($

N

$1$

$)$

$=$

L

$($

N

$4$

$)$

$!=$

L

$($

N

$3$

$)$

L$($N

$1$

$$

$)=$L$($N

$4$

$$

$)$

$$

$$

$=$L$($N

$3$

$$

$)$

Choice $4$ of $4$: Neither, namely

L

$($

N

$1$

$)$

$!=$

L

$($

N

$3$

$)$

L$($N

$1$

$$

$)$

$$

$$

$=$L$($N

$3$

$$

$)$ and

L

$($

N

$1$

$)$

$!=$

L

$($

N

$4$

$)$

L$($N

$1$

$$

$)$

$$

$$

$=$L$($N

$4$

$$

$).$