part-ii/2021-26/

[tripos-comments[bot]]

Part II 2021 Automata and Formal Languages: Paper 4, Section I, $4 \mathrm{~F}$

https://questions.tripos.org/part-ii/2021-26/

[artie2000]

(i)

Yes: given by regular expression $(01)^\star01$.

(ii)

No: let $n$ be the pumping constant, and pump $0^n1^{2n}0^n$ down.

(iii)

Yes: the complement is given by the obvious DFA.