"Context-Free Grammars & Pushdown Automata" — Practice

Question 1

Context-free languages are NOT closed under which operation?

Accepted Answer

C

Question 2

Which production is allowed in Chomsky normal form?

Accepted Answer

B

Question 3

Which language requires a nondeterministic pushdown automaton?

Accepted Answer

B

Question 4

Write a context-free grammar for the language of strings over {a, b} with equal numbers of a's and b's, and derive the string abba.

Accepted Answer

The language allows the a's and b's in any interleaving, provided the totals match. That rules out the simple nested grammar and requires a construction that permits both orders.

S goes to aSbS, or bSaS, or epsilon.

The reasoning: any non-empty balanced string begins with either an a or a b. If it begins with a, then somewhere later there is a matching b, and the parts before and after that b are each independently balanced. The production aSbS captures exactly that decomposition, and bSaS captures the mirror case.

Derive abba. The string begins with a, so use S goes to aSbS.

S gives aSbS. Take the first S to epsilon: a b S. That leaves ab followed by whatever the second S produces, and the remainder to produce is ba.

Expand the second S with bSaS: ab then bSaS. Take both inner S symbols to epsilon, giving abba.

The full derivation is S, then aSbS, then abS, then abbSaS, then abbaS, then abba.

A check: the grammar cannot produce an unbalanced string, because every production adds exactly one a and one b or nothing at all, so the counts stay equal at every step.

Question 5

Show that the grammar S goes to SS, or aSb, or epsilon is ambiguous, and identify what causes the ambiguity.

Accepted Answer

The language is the set of balanced bracket strings, reading a as an opening bracket and b as a closing one.

Consider the string ab, which is a single matched pair.

Tree 1: apply S goes to aSb at the root, with the inner S deriving epsilon. That gives ab directly with one production plus one epsilon.

Tree 2: apply S goes to SS at the root. Let the first S derive ab by the route above, and the second S derive epsilon. That also gives ab.

The two trees are structurally different — one has a single aSb node, the other has an SS node above it — so the grammar is ambiguous.

The cause is that S goes to SS combined with S goes to epsilon allows an unbounded number of empty concatenations to be inserted anywhere. Every string can be padded with any number of epsilon-deriving S nodes, giving infinitely many parse trees for every string in the language.

The fix is to prevent an S from deriving epsilon inside the concatenation. One unambiguous grammar is: S goes to aSbS or epsilon. Here every non-empty string is decomposed uniquely by locating the b that matches the very first a, and the concatenation production has been folded into the same rule so no free-standing SS node exists.

Note that the language itself is not inherently ambiguous, since an unambiguous grammar exists. Ambiguity was a defect of the first grammar rather than of the language.

Question 6

Design a pushdown automaton accepting strings over {a, b} where the number of a's exceeds the number of b's, and state whether it is deterministic.

Accepted Answer

Use the stack to hold the running excess of one symbol over the other, storing a marker for whichever symbol is currently in surplus.

Start with a bottom-of-stack marker Z.

On reading a: if the top is Z or an A marker, push an A. If the top is a B marker, pop it — one a has cancelled one surplus b.

On reading b: if the top is Z or a B marker, push a B. If the top is an A marker, pop it.

The stack therefore always holds the absolute difference between the counts, marked with the symbol currently in excess, sitting above the bottom marker Z.

Acceptance: at the end of input, accept if the top of the stack is an A marker, meaning at least one a is in surplus.

This PDA is deterministic. Every move is determined completely by the current input symbol and the top stack symbol, with no choice anywhere and no epsilon-moves that compete with a symbol-consuming move.

The language is therefore a deterministic context-free language, which fits the general pattern: languages needing one comparison with an observable trigger are deterministic, while those needing a guess are not.

A check on the boundary: the empty string leaves Z on top, which is not an A marker, so it is rejected — correct, since zero a's do not exceed zero b's.

Question 7

Prove that context-free languages are not closed under complement, using only closure under union and non-closure under intersection.

Accepted Answer

The argument is by contradiction and uses De Morgan's law.

First, establish the two facts being assumed. Context-free languages are closed under union: given grammars for L1 and L2 with start symbols S1 and S2, adding a new start symbol S with the production S goes to S1 or S2 generates the union, and the result is still context-free.

Context-free languages are not closed under intersection. The witness is L1 as the strings a to the n, b to the n, c to the m, and L2 as the strings a to the m, b to the n, c to the n. Both are context-free, since each requires only one comparison and permits the third symbol group to vary freely. Their intersection forces all three counts equal, giving the language a to the n, b to the n, c to the n, which is not context-free.

Now suppose, for contradiction, that the class were closed under complement.

By De Morgan, the intersection of L1 and L2 equals the complement of the union of the complements of L1 and L2.

Working outward: the complement of L1 would be context-free by assumption, and so would the complement of L2. Their union would be context-free by closure under union. And the complement of that union would be context-free by the assumption again.

But that final language is exactly the intersection of L1 and L2, which we established is not context-free.

The contradiction shows the assumption is false, so context-free languages are not closed under complement.

The same argument run in reverse explains why deterministic context-free languages, which are closed under complement, cannot be closed under union — otherwise they would be closed under intersection, and the same witness applies.

Question 8

Simplify the grammar S to aA or a or BD, A to aA or epsilon, B to aB, D to ddd, showing each step in the correct order.

Accepted Answer

Follow the standard order: epsilon-productions, then unit productions, then non-generating symbols, then unreachable ones.

Step 1, epsilon-productions. Only A derives epsilon directly. Find every production mentioning A and add a version with A deleted.

S to aA becomes S to aA or S to a. The second already exists, so nothing new.
A to aA becomes A to aA or A to a.

Remove A to epsilon. The grammar is now: S to aA or a or BD; A to aA or a; B to aB; D to ddd.

Step 2, unit productions. A unit production has a single variable on the right. Scanning the productions, none has that shape, so there is nothing to remove.

Step 3, non-generating symbols. A symbol generates if it can derive a string of terminals.

D to ddd, so D generates. A to a, so A generates. S to a, so S generates.
B to aB is B's only production, and it requires B itself to generate. B has no terminal-only alternative, so B is non-generating.

Remove B and every production mentioning it. That deletes B to aB and also S to BD, since that production depends on B.

The grammar is now: S to aA or a; A to aA or a; D to ddd.

Step 4, unreachable symbols. From S we reach A through S to aA. We never reach D, because the only production that mentioned D was S to BD, which step 3 deleted.

Remove D. The final grammar is: S to aA or a; A to aA or a.

The language is one or more a's.

The order mattered twice here. Removing the non-generating B is what made D unreachable, so a reachability check performed first would have kept D and required a second pass.

Question 9

Explain why deterministic context-free languages are closed under complement while general context-free languages are not, and why the deterministic class is not closed under union.

Accepted Answer

Closure under complement for the deterministic class follows the same argument as for DFAs, with one extra care.

A deterministic pushdown automaton has exactly one computation path on any input, so the string is either accepted or rejected by that single path, with no ambiguity. Swapping the accepting and non-accepting states therefore inverts the language exactly.

The extra care concerns machines that loop forever on epsilon-moves or that halt prematurely by emptying the stack. Both must first be eliminated by a standard construction that makes the machine read its entire input and always reach a well-defined final configuration. Once that normalisation is done, the swap works.

For the general class the argument collapses, because a nondeterministic PDA can have many computation paths. A string with one accepting and one rejecting path is accepted by the original machine and also by the swapped one, so the swap does not complement the language. This is the same failure as for NFAs, but with a crucial difference: for finite automata the repair is to determinise first, whereas for pushdown automata determinisation is impossible in general, since the deterministic class is strictly smaller.

For union, the deterministic class fails precisely because it is closed under complement. Suppose it were also closed under union. Then by De Morgan it would be closed under intersection, since the intersection is the complement of the union of the complements. But the same witness that defeats the general class defeats this one: two deterministic context-free languages whose intersection requires three equal counts. That intersection is not even context-free, let alone deterministic.

So the deterministic class gets complement and loses union, and the general class gets union and loses complement. Exactly one of the two can hold given that intersection fails for both.

Practice — "Context-Free Grammars & Pushdown Automata"

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