- L
_{1}is context-free. A CF grammar which generates L_{1}is:S -> AB

_{1}| B_{2}C

A -> aA | lambda

B_{1}-> bB_{1}c | lambda

C -> cC | lambda

B_{2}-> aB_{2}b | lambda - L
_{2}is context-free. A CF grammar which generates L_{2}is:S -> AC

A -> aAb | lambda

C -> bCc | lambda - L
_{3}is not context-free. Given a natural number n, consider the string a^{n}b^{2n}c^{n}and show that contradicts the pumping lemma.

S -> ABFrom this grammar we can easily construct the deterministic PDA. Informally, the PDA will accept a sequence of b's and put them on the stack, then will accept a sequence of c's and d's, alternated arbitrarily, and pop all the b's from the stack. When the stack is empty, will accept a sequence of a's.

A -> bAC | lambda

B -> lambda | aB

C -> c | d

- scan the tape from left to right (skipping the x's and the y's) until you find an a or a b. Change it to x. If no a or b are found, then halt (accept).
- continue scanning from left to right until you find a b (if in (1) you found an a) or an a (if in (1) you found a b). Change it to y.
- go back on the tape from left to right (skipping the y's) until you find an x. Go to point (1).

- L
_{1}is not RE. In fact, the propertyp

is not finitely reachable (Even is infinite). Then by the theorem of Rice-Shapiro L_{1}(L) = Even is contained in L_{1}is not RE. - L
_{2}is RE. In fact, we can semidecide that e(M) belongs to L_{2}: one way is to generate all the strings of even length, and try them "in parallel" on the machine M. As soon as one of them is accepted by M (if any), we halt and accept e(M).

However, L_{2}is not Rec. To prove this, note that the the propertyp

is not trivial. In fact, p_{2}(L) = the intersection between Even and L is not empty_{2}({aa}) holds and p_{2}({}) does not hold. Hence by the theorem of Rice L_{2}is not Rec.

Another way to prove that L_{2}is not Rec is by observing that L_{3}is not RE (see next point). - L
_{3}is not RE. To prove this, note that the propertyp

is not upward-closed. In fact, p_{3}(L) = the intersection between Even and L is empty_{3}({}) holds and p_{3}({aa}) does not hold. Then by the theorem of Rice-Shapiro L_{3}is not RE. - L
_{4}is Rec. In fact, given a string x, we can decide whether x belongs to L_{4}by checking that x is in the right format (i.e. that x is the encoding of a TM) and that x has even length. Note that the theorems of Rice and of Rice-shapiro do not apply here, since L_{4}is described by an intentional property of machines, not an extensional one.