Problem Solving in Automata, Languages, and Complexity

278 COMPUTABILITY THEORY

3. Complete the details of the PDA Ml of Example 5.43. That is, construct
   a PDA A& which accepts the set {my 1 x and y are two legal configuration
   codes of M, and neg(a: t- y’i)).

* 4. For each of the following problems about context-free grammars, deter-

mine whether it is decidable or not:

(a) Given a context-free grammar G and a DFA M, determine

whether L(G) C - L(M).

(b) Given a context-free grammar G and a DFA M, determine

whether L(M) C L(G).

(c) Given a context-free grammar G, determine whether L(G) is reg-

ular.

(d) Given a context-free grammar G, determine whether the comple-

ment of L(G) is context-free.

(e) Given two context-free grammars Gi and G2, determine whether

L(G1) n L(G2) is context-free.

* 5. For each of the following variations of PCP, determine whether it is

decidable or not:

( > a

04

( > C

(4

( 1 e

The problem PCP over the alphabet C = { 1).

The problem PCP over the alphabet C = (0, 1).

Given a finite set of ordered pairs (~1, yl),... , (x,, yn) of strings

in C*, determine whether there is an infinite sequence (il, i2,... )

of integers in { 1,... , n) such that xi1 xi2 l l l = yil yiZ l. l.

Given a finite set of ordered pairs (~1, yl),... , (xn, yn) of strings

in C*, determine whether there exist two sequences of integers (il,

i2,. ..) i/c) and (jl,j2, l l l J-e), with each element belonging to { 1,

... 7 n), such that zil xi,. l 4 xi, = yjl yj2 l. l yjl.
The same question as (d) above, except that the two sequences of
integers must be of the same size, that is, k = !.

* 6. In this question, we consider the tiling problem. In this problem, a

colored tile is a square tile of size 1 x 1 whose four sides are colored by

colors selected from a finite set C. The four sides of a colored tile is

clearly marked to be the up, down, left and right sides. Two colored

tiles can be put in the plane next to each other if the two neighboring

sides have the same color.

TILING. Given a finite number of types to, tl,... , t, of colored

tiles, determine whether it is possible to cover the first quad-

rant of the plane by colored tiles of these types (with infinite

supply of the tiles of each type), starting with a tile of type

to at the lower left corner (see Figure 5.6).