(2p) [AB] Construct an NFA (without ε-transitions) that recognises the same language over {0, 1} as the regular expression (0 + 01*)*(ε + 1)1(ε + 0 + 1)*.
You do not have to use any of the methods presented in the course (but this is of course allowed). Do not just give an answer, explain your solution.
(2p) [AB] Construct a regular expression for the language over {0, 1} that consists of every string w ∈ {0, 1}* that satisfies the following conditions:
|w| ≥ 2.
The first and last symbol in w must be 1.
The string 00 must not occur in w.
A possibly interesting test case: 101.
You do not have to use any of the methods presented in the course. Do not just give an answer, explain your solution.
(3p) [AB] Convert the following ε-NFA to an equivalent DFA:
| ε | a | b | |
|---|---|---|---|
| → s₀ | ∅ | {s₁} | {s₀, s₂} |
| s₁ | {s₂} | {s₄} | {s₃} |
| s₂ | ∅ | {s₁, s₄} | {s₃} |
| s₃ | {s₅} | {s₄, s₅} | ∅ |
| s₄ | {s₃} | ∅ | {s₅} |
| * s₅ | ∅ | {s₅} | {s₅} |
You can use any of the methods discussed during the course. Do not just give an answer, show how you construct the DFA.
(3p) [AB] Convert the following NFA to an equivalent regular expression:
| a | b | c | |
|---|---|---|---|
| → s₀ | {s₀} | {s₁} | {s₂} |
| s₁ | ∅ | {s₃} | {s₂} |
| s₂ | ∅ | {s₁} | {s₄} |
| s₃ | {s₄} | ∅ | {s₃} |
| * s₄ | ∅ | {s₄} | ∅ |
You can use any of the methods discussed during the course. Do not just give an answer, show step by step how you construct the regular expression.
(Exercises marked with [AB] are based on exercises from a previous version of this course, given by Ana Bove.)