COMP 330 - Fall 2020 - Assignment 6 1

COMP 330 - Fall 2020 - Assignment 6

1. Rigorously establish the decidability or undecidability of the following languages:

(a) (20 Points)

L = {0 n |the decimal expansion of π = 3.14 . . . contains n (or more) consecutive 0’s}.

(b) (20 Points)

L = {hDi | D is a DFA and L(D) is not recognized by a DFA with fewer states}.

2. (30 Points) Prove that the following language is undecidable by giving a reduction from the Post Correspondence Problem.

L = {hGi | G is a CFG and L(G) contains at least one palindrome}.

3. (30 Points) Let A be any language in P over the alphabet {0, 1}. Prove that

LA = {1 n | n ∈ N, A ∩ {0, 1} n 6= ∅}

is in NP.