## Description

## Final Take-Home Examination

## Question 1[10 points]

Write a regular expression for the set of all strings over the alphabet {a, b}

in which each a is immediately preceded and immediately followed by a b.

## Question 2[10 points]

Give an algorithm to decide whether the language accepted by a DFA is

Σ

∗

. Your algorithm description should be high-level and does not need to

go into any details. For example you can say “minimize” or “determinize”

without explaining how these algorithms work.

## Question 3[20 points]

One of the following questions is decidable and the other is undecidable.

1. Given a CFL L and a regular language R, is L ∩ R = ∅?

2. Given a CFL L and a regular language R, is L ∩ R = Σ∗

?

For the one that is decidable give an algorithm, for the other give an undecidability proof.

## Question 4[15 points]

Consider the language L = a

n

b

mc

n+m with n, m ≥ 0. Classify this as one

of the three following:

1. regular,

2. context-free but not regular,

3. recursive but not context-free.

You have to prove each asssertion. For example, if you say that it is regular,

you must give an NFA to recognize it; of course, in this case it is obvious

that it does not belong to the other two classes. Similarly, if you claim that

it is context-free, but not regular, you have to give a context-free grammar

and a proof that it is not regular, but, of course you will not have to

prove that it is recursive. If you claim that it belongs to the last class, you

must show that it is not context-free (it is then immediate that it is not

regular) and give an algorithm to recognize it.

## Question 5[15 points]

The set F IN = {hMi|M halts on finitely many inputs}. Explain why this

set is not decidable [2 points]. Explain why this set is not CE, use a reduction

to some known non-CE set like EMPTY. EMP T Y = {hMi|M never halts on any input}.

[13 points].

## Question 6[20 points]

Recall that a set is called cofinite if its complement is finite. Thus if we

are talking about the natural numbers the set of numbers bigger than 17

is cofinite and the set of odd numbers is infinite but not cofinite. For this

question the alphabet is fixed as {a, b}.

1. Is is decidable whether a regular language is cofinite? Assume that

the regular language is defined by giving you its recognizing DFA.

2. Is it decidable whether a context-free language is cofinite?

3. Is it decidable whether a language described by a Turing machine is

cofinite?

Please give short answers. Long answers will be penalized even if they are

correct. You may invoke known theorems from the class, but not random

theorems that you found on the internet.

## Question 7[10 points]

Are the following statements true or false? No explanations are needed.

1. The intersection of two context-free languages can be regular.

2. The intersection of two context-free languages must be recursive.

3. Given G1 and G2 context-free grammars, it is undecidable whether

L(G1) ⊂ L(G2).

4. It is decidable whether a regular language is equal to Σ∗

.

5. All programs written in Python are guaranteed to halt.