Exercise $38$ Short statements

$(9$ points$)$

Which of the following statements about automata and formal languages are true? Briefly justify

your answers. For false statements, it is sufficient to give a counterexample. Answers without any

substantiation will not achieve points!

$($a$)$ There is a regular language with infinitely many Myhill$-$Nerode equivalence classes.

$($b$)$ Any NFA with $n$ states can be converted into an equivalent DFA with at most $2n$ states.

$($c$)$ Let $L$ be a regular language. There is an algorithm that can decide whether at least one word

in $L$ starts with an $a.$

$($Note: You can assume that the regular language is given as an automaton, a regular grammar

or as a regular expression, depending on what model is the most useful for you to use in your

algorithm.$)$

$($d$)$ If A and $C$ are regular languages and AsubeBsubeC, then $B$ must be context$-$free.

$($e$)$ For every context$-$free language $L$ and every regular language $R,$ also $\frac{L}{\frac{?}{?}}R$ is context$-$free.

$($f$)$ For every context$-$free language $L($given as a context$-$free grammar$)$ there is an algorithm, that

solves the word problem for $L.$

$($In total, there are $20$ points in this exercise sheet.$)$