If you cannot access Canvas and submit your answers via email, please only give the answers (a number or a list of numbers), and no motivating arguments.
The first four questions refer to the ε-NFA given by the following transition table:
| ε | 0 | 1 | |
|---|---|---|---|
| → q₀ | {q₁, q₄} | ∅ | ∅ |
| q₁ | ∅ | {q₂} | ∅ |
| q₂ | ∅ | ∅ | {q₃} |
| q₃ | {q₀, q₇} | ∅ | {q₃} |
| q₄ | ∅ | ∅ | {q₅} |
| q₅ | ∅ | {q₆} | ∅ |
| q₆ | {q₀, q₇} | {q₆} | ∅ |
| * q₇ | ∅ | ∅ | ∅ |
(1p) If the ε-NFA is in state q₀ and the next input symbol is 0, what states (if any) is the ε-NFA in after processing this symbol?
q₀
q₁
q₂
q₃
q₄
q₅
q₆
q₇
(1p) If the ε-NFA is in state q₅ and the next input symbol is 0, what states (if any) is the ε-NFA in after processing this symbol?
q₀
q₁
q₂
q₃
q₄
q₅
q₆
q₇
(1p) If the ε-NFA is in state q₀, what states (if any) is the ε-NFA in after processing the string 011?
q₀
q₁
q₂
q₃
q₄
q₅
q₆
q₇
(1p) Which of the following strings (if any) are in the language of the ε-NFA?
ε
00
000001
0110
100001
(1p) Now consider the following ε-NFA:
| ε | 0 | 1 | |
|---|---|---|---|
| → q₀ | {q₁} | ∅ | ∅ |
| q₁ | ∅ | {q₂} | ∅ |
| q₂ | ∅ | ∅ | {q₃} |
| q₃ | {q₀, q₄} | ∅ | {q₃} |
| * q₄ | ∅ | ∅ | ∅ |
If the subset construction for ε-NFAs is applied to this ε-NFA and all inaccessible states are removed, which of the DFAs below is equal, up to renaming of states, to the DFA that is obtained?
| 0 | 1 | |
|---|---|---|
| → A | B | C |
| B | C | D |
| C | C | C |
| * D | B | D |
| 0 | 1 | |
|---|---|---|
| → A | B | C |
| B | C | D |
| C | C | C |
| * D | B | D |
| E | E | E |
| 0 | 1 | |
|---|---|---|
| → A | B | C |
| B | C | D |
| C | C | C |
| * D | B | E |
| * E | B | D |