"Regular & Context-Free Languages: Closure and the Pumping Lemma" — Practice

Question 1

Which machine model corresponds to context-sensitive languages?

Accepted Answer

A

Question 2

A language satisfies the pumping lemma for regular languages. What can be concluded?

Accepted Answer

C

Question 3

Recursively enumerable languages are NOT closed under which operation?

Accepted Answer

D

Question 4

Prove that the language of strings over {a, b} containing a prime number of a's is not regular.

Accepted Answer

Suppose it were regular, and let p be the pumping length supplied by the adversary.

Choose a prime q greater than p, which exists since primes are infinite, and take w to be a to the q. Its length q exceeds p, so the lemma applies.

The adversary decomposes w as xyz with the combined length of x and y at most p and the length of y at least 1. Since w consists only of a's, y is a to the k for some k between 1 and p.

Write the a-counts: x contributes some number, y contributes k, and z contributes the rest, totalling q.

Now pump with i equal to q plus 1. The resulting string has a-count equal to q minus k, plus k times (q plus 1), which simplifies to q plus kq, that is q times (1 plus k).

Since k is at least 1, the factor 1 plus k is at least 2, and q is at least 2 because it is prime and larger than p.

So the a-count is a product of two integers both at least 2, which means it is composite rather than prime.

The pumped string is therefore not in the language, contradicting the lemma, so the language is not regular.

The choice of i was the clever step. Pumping to i equal 2 would give q plus k, which might happen to be prime for a particular k, so it would not defeat every decomposition. Choosing i equal to q plus 1 forces the count to factor for every possible k, which is what a valid proof requires.

Question 5

Prove that the language of strings ww over {a, b} is not context-free.

Accepted Answer

Suppose it were context-free, with pumping length p from the adversary.

Choose the string a to the p, b to the p, a to the p, b to the p. It has the form ww with w equal to a to the p b to the p, so it is in the language, and its length 4p exceeds p.

The adversary decomposes it as uvxyz with the length of vxy at most p and the combined length of v and y at least 1.

The string consists of four blocks of length p each. A window of length at most p can therefore touch at most two adjacent blocks, never three.

Pump with i equal to 2. The pumped string is longer by the combined length of v and y, which is at least 1 and at most p.

For the result to be in the language, it must split into two equal halves that are identical. Its length is 4p plus the pumped amount, so the halves have length 2p plus half the pumped amount.

Consider where the window sat. If it lay entirely within the first half, the first half grows while the second is unchanged. The new midpoint shifts right, so the second half now begins inside what was the first half's material, and the two halves no longer match — the first ends in b's while the second begins with material from the wrong block.

If the window straddled the midpoint, it touches the second a-block and either the preceding b-block or the following b-block, and pumping increases counts asymmetrically between the halves.

If it lay entirely within the second half, the mirror argument applies.

In every case the two halves differ, so the string is not of the form ww and the lemma is violated. The language is not context-free.

Note the contrast with palindromes: ww reversed is context-free because a stack delivers the first half backwards, which is exactly what a reversal needs and exactly wrong for a copy.

Question 6

Place these languages in the Chomsky hierarchy, giving a reason for each: strings with equal a's and b's; strings of the form a to the n b to the n c to the n; strings whose length is a perfect square.

Accepted Answer

Strings with equal a's and b's are context-free but not regular.

Not regular: Myhill-Nerode distinguishes the strings a, aa, aaa and so on pairwise, since appending b to the i accepts exactly the one with i a's, giving infinitely many classes.

Context-free: the grammar S goes to aSbS, or bSaS, or epsilon generates it, decomposing any balanced string at the position matching its first symbol. A single stack suffices because only one running difference must be tracked.

Strings of the form a to the n b to the n c to the n are context-sensitive but not context-free.

Not context-free: the standard window argument. With three blocks of length p, a window of length at most p touches at most two, so pumping leaves the third count unchanged and equality fails.

Context-sensitive: a linear bounded automaton verifies the counts by repeated passes, crossing off one a, one b and one c per sweep until the tape is empty. The tape never exceeds the input length, so the space bound holds.

Strings whose length is a perfect square are context-sensitive but not context-free.

Not context-free: pumping increases the length by a bounded amount, at most p, while consecutive squares grow further apart without bound, so beyond some point the pumped length falls strictly between two squares.

Context-sensitive: a linear bounded automaton can compute successive squares on the tape and compare, all within space proportional to the input.

The pattern is that each level is separated by a specific structural demand: one nesting for context-free, more than one simultaneous comparison for context-sensitive.

Question 7

Construct a non-regular language that satisfies the regular pumping lemma, and prove both claims.

Accepted Answer

Take the language L consisting of all strings a to the i, b to the j, c to the k where either i equals 0, or j equals k.

First, L satisfies the pumping lemma with pumping length p equal to 1.

Let w be any string in L of length at least 1. Two cases arise.

Case A: w begins with an a. Then i is at least 1, so membership must come from the second clause, meaning j equals k. Decompose with x empty, y equal to the single leading a, and z the remainder. Pumping produces a to the i', b to the j, c to the k for various i' including zero. If i' is zero the first clause holds; if i' is positive the second clause still holds since j and k are untouched. Every pumped string is in L.

Case B: w begins with a b or a c. Then i equals 0 and the first clause holds. Decompose with y as the first symbol. Pumping changes the b or c count but leaves i at zero, so the first clause continues to hold and every pumped string is in L.

So every sufficiently long string pumps successfully and the lemma is satisfied.

Second, L is not regular. Apply Myhill-Nerode to the strings a b, a b b, a b b b and so on — that is, a single a followed by j b's.

Take two such strings with different b-counts j and j'. Append c to the j. The first becomes a, b to the j, c to the j, which has j equal to k and is in L. The second becomes a, b to the j', c to the j, which has a positive i and unequal b and c counts, so it is not in L.

The suffix distinguishes every pair, so there are infinitely many equivalence classes and L is not regular.

The language therefore satisfies the pumping lemma and is not regular, which demonstrates that the lemma is necessary but not sufficient and that no pumping argument could ever establish regularity.

Question 8

Prove that if a language and its complement are both recursively enumerable, the language is decidable, and derive the non-closure of recursively enumerable languages under complement.

Accepted Answer

Let L be recursively enumerable and suppose its complement is too. Then there are Turing machines M1 semi-deciding L and M2 semi-deciding the complement.

Semi-deciding means the machine halts and accepts on every member of its language, and may run forever on non-members. Crucially, neither machine can be relied on to reject.

Construct a new machine M that, on input x, simulates M1 and M2 in parallel by interleaving their steps: one step of M1, one step of M2, one step of M1, and so on.

Every string x lies in exactly one of L or its complement, since the two partition the set of all strings. So exactly one of M1 and M2 will eventually halt and accept on x.

If M1 halts first, M outputs yes. If M2 halts first, M outputs no.

M always halts, because one of the two simulations is guaranteed to terminate, and the interleaving ensures neither can be starved by the other running forever. M therefore decides L, so L is recursive.

That establishes the positive claim: both a language and its complement being recursively enumerable implies decidability.

The non-closure result follows immediately. Suppose the recursively enumerable languages were closed under complement. Then for every recursively enumerable L, the complement would also be recursively enumerable, and by the argument above L would be decidable.

That would make every recursively enumerable language recursive, so the two classes would coincide.

But they do not. The halting language is recursively enumerable, since a universal machine can simulate the encoded machine and accept if it halts, and it is undecidable by the standard diagonalisation argument.

The contradiction shows the class is not closed under complement. The complement of the halting language is the standard example of a language that is not even recursively enumerable.

Question 9

Prove that the language of strings a to the i, b to the j with i greater than j is not regular, and explain why pumping down rather than up is the natural choice.

Accepted Answer

Suppose it were regular, with pumping length p supplied by the adversary.

Choose w equal to a to the (p plus 1), b to the p. It is in the language since p plus 1 exceeds p, and its length exceeds p so the lemma applies.

The adversary decomposes w as xyz with the combined length of x and y at most p, and the length of y at least 1.

Because the first p symbols of w are all a's, both x and y consist entirely of a's, and y is a to the k for some k between 1 and p.

Now pump down by choosing i equal to 0, which deletes y.

The resulting string is a to the (p plus 1 minus k), b to the p.

Since k is at least 1, the a-count is at most p, while the b-count is exactly p. The condition requiring strictly more a's than b's therefore fails, and the string is not in the language.

The lemma is violated, so the language is not regular.

As to why pumping down is natural here: the language is defined by a strict inequality with a's on the larger side. Pumping up adds a's, which only strengthens the inequality and keeps the string inside the language, so no contradiction arises. Pumping down removes a's, which is exactly the direction that can violate the inequality.

The general principle is to pump in the direction that attacks the defining constraint. For a lower bound on a count, delete; for an upper bound or an exact equality, either direction may work but adding is usually simpler. Choosing the witness with the a-count only just exceeding the b-count is the other half of the trick, since it means removing even one a breaks the condition.

Practice — "Regular & Context-Free Languages: Closure and the Pumping Lemma"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities