CIS 573 Homework, due April 17

1. Exercises 6.2-1, 6.4-2(a,b), 6.4-8(b), 6.5-3, 6.6-1, 6.8-2

1. Exercises 6.4-5, 6.4-7(b,c), 6.4-8(c)
2. 1. Prove that {a^hbⁱc^jd^k : h ≠ j and i ≠ k} is not a CFL. Hint: Apply Ogden's lemma to a^N+N!b^Nc^Nd^N+N! twice and use the fact that if subtrees overlap then one is contained in the other.
   2. Prove that {a^hbⁱc^jd^k : h = j and i ≠ k} is not a CFL.
3. Prove or disprove: If L is a CFL then L ∩ a*b* is an NCA language.
4. Prove or disprove:
   1. If L is an NCA language over a 2-character alphabet, then PERM(L) is a CFL.
   2. If L is an NCA language over a 2-character alphabet, then PERM(L) is an NCA language.
   3. If L is a CFL over a 2-character alphabet, then PERM(L) is a CFL.
   4. If L is a CFL over a 2-character alphabet, then PERM(L) is an NCA language.