T Naughton, CS NUIM

QB1 Hint: In lexicographical order, the language is L = {#00, #01, #10, #11, 0#00, 0#01, 0#10, 0#11, 1#00, 1#01, 1#10, 1#11, 00#01, 00#10, 00#11, 01#00, 01#01, 01#11, 10#00, 10#10, 10#11, 11#00, 11#01, 11#10, 000#01, 000#10, 000#11, 001#01, 001#11, 010#00, 010#11, 011#01, ...}. Each word in L consists of a binary string w followed by a # followed by a two-bit binary string c where the reverse of c is not in w.

We will prove that L is context-free by constructing a CFG that generates it. The following CFG generates L:

S A#00 | B#01 | C#10 | D#11
A OE | E
E 10E | 1E | e
B 0B1 | e
C 1C0 | e
D 1F | F
F 01F | 0F | e

This CFG generates L. Since there is a theorem that states that a language is context-free if and only if it is generated by a CFG, then this proves that L is context-free.

QB2 We will prove that L is decidable by constructing a TM that decides it. The following TM decides L:

"On input w:
   1. Scan through the word until a # is reached and then memorise the next two symbols. Hint: For example, go into state 50 if the two symbols were '00', go into state 51 if the two symbols were '01', go into state 52 if the two symbols were '10', and go into state 53 if the two symbols were '11'. If there is more or less than one # in the word or if there is more or less than two symbols after the # then reject.
   2. Go back to the beginning of the word.
   3. If the two symbols were '00', then reject if '00' appears anywhere before the #.
   4. If the two symbols were '01', then reject if '10' appears anywhere before the #.
   5. If the two symbols were '10', then reject if '01' appears anywhere before the #.
   6. If the two symbols were '11', then reject if '11' appears anywhere before the #.
   7. Accept."

This TM decides L. Since there is a theorem that states that a language is decidable if and only if it is decided by a TM, then this proves that L is decidable.

QB3A We will prove that L is regular by constructing a regular expression that specifies it. The following regular expression specifies L:

(0 e)(10 1)*#00
0*1*#01
1*0*#10
(1 e)(01 0)*#11

(Line breaks have been inserted to make it easier to read.)

This regular expression specifies L. Since there is a theorem that states that a language is regular if and only if it is specified by a regular expression, then this proves that L is regular.