Sketch of Solutions to Exercises

1.4.2

1.4.3

(a)

For a given G =< N, , P, S > and a string w try all derivations S _{1 2} ... _i for i > 1 until the string w = _i is encountered.

(b)

For a given G =< N, , P, S > try all derivations S _{1 2} ... _i until a string of terminal sybols is encountered.

1.4.4 For a given (G, x) try all derivations S * s.t. || < |x|.

1.4.5 For a grammar G let L_i(G) denote the set of all strings in L(G) of length i. For the given (G₁, G₂) determine L_i(G₁) and L_i(G₂), i = 0, 1, 2, ... Declare G₁ /= G₂ when an i such that L_i(G₁) /= L_i(G₂) is reached.

1.4.6 Type 3 grammars are special cases of type 0 grammars. As a result

• Decidability of the emptiness problem for type 0 grammars implies decidability of the emptiness problem for type 3 grammars.
• Undecidability of the emptiness problem for type 3 grammar implies undecidability of the emptiness problem for type 0 grammars.

1.4.7

(a)

Given Q(x₁, ..., x_n) try all assignments to (x₁, ..., x_n) in canonical ordering, i.e.,

  0, ..., 0    0's only 
  O, ..., 1    0's and 1's only 
       . 
       . 
       . 
  1, ..., 1 
  0, ..., 2    0's,  1's, and 2's  only 
       . 
       . 
       . 
  2, ..., 2 
       . 
       . 
       . 

(b)

Given (P ₁, P ₂) try all inputs to P ₁ and P ₂ in canonical ordering.