Exercise $25$ Decidability ${?}_{(}())$

$(5$ points$)$

Prove that the following problems are decidable by giving an algorithm for each problem that solves

it$.$ Assume that each language is given by a deterministic finite automaton. Justify the correctness of

your algorithms!

$($a$)$ Let $L_1,L_2$ be regular languages. Does the intersection of $L_1$ and $L_2$ contain infinitely many

words?

$($b$)$ Let Lsube${}^{**}$ be a regular language and let $n$ be a natural number. Does $L$ contain a word with

length greater than $n?$

$($c$)$ Let $L_1,L_2$ be regular languages. Does the union of $L_1$ and $L_2$ contain finitely many words?

$($Note: Your algorithms can use the algorithms presented in the lecture.$)$

$($Note: In this task the question is not whether these properties hold for arbitrary languages, but to

create algorithms that can check these properties for some specific languages.$)$