Paper 3, Section I, F

Automata and Formal Languages
Part II, 2021

Define a regular expression RR and explain how this gives rise to a language L(R)\mathcal{L}(R).

Define a deterministic finite-state automaton DD and the language L(D)\mathcal{L}(D) that it accepts.

State the relationship between languages obtained from regular expressions and languages accepted by deterministic finite-state automata.

Let LL and MM be regular languages. Is LML \cup M always regular? What about LML \cap M ?

Now suppose that L1,L2,L_{1}, L_{2}, \ldots are regular languages. Is the countable union Li\bigcup L_{i} always regular? What about the countable intersection Li\bigcap L_{i} ?