Hey, here are some of my interesting ideas when I was studying those courses.

I am doing these just for fun :)

Question 1:

Please analyze which of the categories does the following languages belong to?

L1= {<A, B>| There is marriage between A and B.}

L2= {<A, B>| There is love between A and B.}

L3= {<A, B, C>| There is marriage in A, B and C.}

L4= {<A, B, C>| There is love in A, B and C.}

l Regular

l Context Free, but not Regular

l Not Context Free

l P

l NP

l NP-Complete

l Decidable

l Recognizable, but not Decidable

l Not Recognizable

Answer:

(1) L1= {<A, B>| There is marriage between A and B.}

L1 is in P (Decided by a deterministic Turing Machine in Polynomial Time). Let M be a Turing Machine that decides L1.

M= “On input <A, B>

        Search if there is a certificate of marriage for them;

        If there is, then accept;

        If not, then reject;”

The time cost of this algorithm is bounded by |n1|+|n2|. (n1、n2 correspondingly are the total numbers of all the stuffs for A and B when searching.) So L1 can be deterministically decided in polynomial time, and it is in P. 

(2) L3= {<A, B, C>| There is marriage in A, B and C.}

L3 is in NP (Decided by a non-deterministic Turing Machine in Polynomial Time). Let M be a Turing Machine that decides L3.

M= “On input <A, B, C>

        Non-deterministically guess two of them;

        Search if there is a certificate of marriage for these two;

        If there is, then accept;

        If not, then reject;”

The time cost for each guess and search is bounded by MAX1≤i<j≤3 {|ni|+|nj|}, and there are at most 3 guess times. So totally, the time cost is bounded by 3* MAX1≤i<j≤3 {|ni|+|nj|}, still polynomial. Therefore, L3 can be non-deterministically decided in polynomial time, and it is in NP.

(3) L2= {<A, B>| There is love between A and B.}

L2 is Recognizable, but not Decidable.   Let M be a Turing Machine that recognizes L2.

M= “On input <A, B>

        Find if they both fall in love with each other;

        If they do, then accept;

        If they don’t have any feelings on each other, then reject;

          If (most likely) one of them is falling in love with the other, but the other one doesn’t feel the same way. In this less encouraging case, the first one may give up, or may need to try, chase, and wait for an unknown time (maybe forever, who knows…)”

So in this way, we can only build a recognizer for L2. We are not sure whether the Turing Machine M will halt in the end or not. Therefore, L2 is Recognizable, but not Decidable.