*l b) The operation L/a, defined in Exercise 4.2.2. Hint: Again, start with a CNF grammar for L.

!! c) cycle, defined in Exercise 4.2.11. Hint: Try a PDA-based construction.

Exercise 7.3.2: Consider the following two languages:

Li = {а Ь2 с 7i,m>0} Lo = {аЧ < I ji,m>0}

a) Show that each of these languages is context-free by giving grammars for each,

! b) Is Li n La a CFL? Justify your answer.

и Exercise 7,3.3; Show that the CFLs are not closed under the following operations:

* a) min, as defined in Exercise 4,2,6(a).

b) max, as defined in Exercise 4,2,6(b).

c) half, as defined in Exercise 4.2.8.

d) alt, as defined in Exercise 4.2.7.

Exercise 7.3.4: The shuffle of two strings w and x is the set of ail strings that one can get by interleaving the positions of w and x in any way. More precisely, shuffle{w, x) is the set of strings z such that

1. Each position of z can be assigned to w or x, but not both.

2. The positions of z assigned to w form w when read from left to right.

3. The positions of z assigned to x form x when read from left to right.

For example, if w = 01 and x = 110, then shuffle{Ol, 110) is the set of strings {OHIO, 01101,10110,10101,11010,11001}. To illustrate the necessary reasoning, the third string, 10110, is justified by assigning the second and fifth positions to 01 and positions one, three, and four to 110. The first string, OHIO has three justifications. Assign the first position and either the second, third, or fourth to 01, and the other three to 110. We can also define the shuffle of languages, shuffie{L-i, L) to the the union over all pairs of strings, w from Li and x from L2, of shuffle(w, x).

a) What is shuffie{00, Ш)?

* b) What is shuffle{Lub2) if Li = L(0*) and Lj = {0 1 n > 0}. *! c) Show that if Li and L2 are both regular languages, then so is

Hint: Start with DFAs for Li and L2-

I d) Show that if i is a CFL and Д is a regular language, then shuffle{L, R) is a CFL. Hint: start with a PDA for L and a DFA for R.

!! e) Give a counterexample to show that if Li and L are both CFLs, then shuffle{Li, L2) need not be a CFL.

!! Exercise 7.3.5: A string у is said to be a permutation of the string x if the symbols of у can be reordered to make i. For instance, the permutations of string X = Oil are 110, 101, and Oil. If L is a language, then perm{L) is the set of strings that are permutations of strings in L. For example, if L = {0 1 I тг > 0}, then perm(L) is the set of strings with equal numbers of Os and Is.

a) Give an example of a regular language L over alphabet {0,1} such that perm{L) is not regular. Justify your answer. Hint: Try to find a regular language whose permutations are all strings with an equal number of Os and Is.

b) Give an example of a regular language L over alphabet {0,1,2} such that perm(L) is not context-free.

c) Prove that for every regular language L over a two-symbol alphabet, perm(L) is context-free.

Exercise 7.3.6: Give the formal proof of Theorem 7.25: that the CFLs are closed under reversal.

Exercise 7.3.7: Complete the proof of Theorem 7.27 by showing that

{qp,w,Zo) (9,e,7)

if and only if {{qp,qA},w, Zo) , £,7) &nd p = 6(pA,w).

7.4 Decision Properties of CFLs

Now, let us consider what kinds of questions we can answer about context-free languages. In analogy with Section 4.3 about decision properties of the regular languages, our starting point for a question is always some representation of a CFL - either a grammar or a PDA. Since we know from Section 6.3 that we can convert between grammars and PDAs, we may assume we are given either representation of a CFL, whichever is more convenient.

We shall discover that very little Cem be decided about a CFL; the major tests we are able to make are whether the language is empty and whether a given

string is in the language. We thus close the section with a brief discussion of the kinds of problems that wc shall later show (in Chapter 9) are undecidable, i.e., they have no algorithm. We begin this section with some observations about the complexity of converting between the grammar and PDA notations for a language. These calculations enter into any question of how efficiently we can decide a property of CFLs with a given representation.

7.4 Л Complexity of Converting Among CFGs and PDAs

Before proceeding to the algorithms for deciding questions about CFLs, let us consider the complexity of converting from one representation to another. The running time of the conversion is a component of the cost of the decision algorithm whenever the language is given in a form other than the one for which the algorithm is designed.

In what follows, we shall let n be the length of the entire representation of a PDA or CFG. Using this parameter as the representation of the size of the grammar or automaton is coarse, in the sense that some algorithms have a runrung time that could be described more precisely in terms of more specific parameters, such as the number of variables of a grammar or the sum of the lengths of the stack strings that appear in the transition function of a PDA.

However, the total-length measure is sufficient to distinguish the most important issues: is an algorithm linear in the length (i.e., does it take little more time than it takes to read its input), is it exponential in the length (i.e., you can perform the conversion only for rather small examples), or is it some nonlinear polynomial (i.e., you can run the algorithm, even for large examples, but the time is often quite significant).

There are several conversions we have seen so far that are linear in the size of the input. Since they take linear time, the representation that they produce as output is not only produced quickly, but it is of size comparable to the input size. These conversions are:

1. Converting a CFG to a PDA, by the algorithm of Theorem 6.13,

2. Converting a PDA that accepts by final state to a PDA that accepts by empty stack, using the construction of Theorem 6.11,

3. Converting a PDA that accepts by empty stack to a PDA that accepts by final state, using the construction of Theorem 6.9.

On the other band, the running time of the conversion from a PDA to a grammar (Theorem 6.14) is much more complex. First, note that n, the total length of the input, is surely an upper bound on the number of states and stack symbols, so there cannot be more than variables of the form [pXq] constructed for the grammar. However, the running time of the conversion can be exponential, if there is a transition of the PDA that puts a large number of symbols on the stack. Note that one rule could place almost n symbols on the stack.