And add new start symbol swith the productionss

CS481F01 Prelim 2 Solutions

A. Demers

CFL. This is clearly the union of two DCFLs, and thus is a CFL. To see it is not deterministic, note that taking the complement and then intersecting with the regular set a∗b∗c∗yields the set

{ aibjck| i ̸= j ∧ i ̸= k }

1

REGULAR. The conditions must hold for every prefix x of w. Thus, the letter counts of a′s, b′s and c′s cannot differ by more than 2 at any point, and can be checked continuously by a finite automaton.

{ w | (∀i, 1 ≤ i ≤ |w|)(|nb(w, i)| ≤ 2 ∨ |nc(w, i)| ≤ 2) }

If there were two universal quantifiers, “under” the ∨ operator, we would have

So what is the answer? This is a DCFL. (In fact, it’s a deterministic 1-counter language, but that wasn’t one of the choices). To see this, consider scanning w from left to right, keeping track of both nb(w, i) and nc(w, i). Initially, do this with the finite states. Suppose nb(w, i) grows outside the range [-2,2]. At that point begin using the stack to maintain nb(w, i). When the value returns to the range [-2,2], switch back to maintaining nb(w, i) in the finite states. (This is easy to detect, e.g. by using a different symbol for the bottom two characters of the stack.) Similarly, whenever nc(w, i) goes out of range, use the stack to maintain nc(w, i). The language definition requires that at most one of nb(w, i) and nc(w, i) can be out of range at any point; thus at most one of them needs the stack. The choice of which counter needs the stack can be made

2

DCFL. This language can be recognized by a product machine consisting of a deterministic PDA as for part (a) running in parallel with a deterministic finite automaton that makes sure the numbers of a′s and c′s always remain within 2 of one another.

2 (25 pts). Recall a CFG is linear if no production has more than one non-terminal in its right hand side; that is, every production is of the form

A → a or A → aB

This is a right-linear grammar; it generates a regular set. There are many non-regular linear languages – the palindromes, for example.

Union the nonterminal and production sets, and add a new start symbol S′with the productions

S′→ S1 | S2

S′→ S′c | A

A → aAb | ab

Since the linear languages are closed under union but not under intersection, they cannot be closed under complement.

follows. Given an input string x = a1a2 . . . an, execute the following code:

The type (1) productions are just as in CNF, and are handled by the first loop of the algorithm. The type (2) productions are handled by an additional assignment outside the innermost loop. Type (3) productions are handled by a

5

The running time is still dominated by the inner loop, which is easily seen to

be O(n3).

In lecture we proved the Chomsky-Schutzenberger Theorem: every CFL L can

be expressed as

(∃z ∈ Σ∗)( h−1(z) = ∅ )

But your h must be 1-to-1 and must be defined on every element of Γ∗. You should explain why your answer is correct; a formal proof is not necessary.

Thus, the image of any word in Γ∗can be decoded uniquely by breaking it into blocks of exactly m symbols each, then counting the leading 0’s in each block.

Of course, there is a similar solution that uses binary rather than unary encoding of ai.

w ∈ DSm ⇒ gm(w) ∈ DS2
w ∈ (B∗m− DSm) ⇒ gm(w) ∈ (B∗2− DS2)

and gm is 1-to-1, then it is a correct solution. Why?

The argument that this homomorphism is 1-to-1 goes just as in part (a). For the rest, observe that

for suitably chosen natural number m, homomorphism h, and regular set R.

8