Home » CS138


Solutions to selected problems in Formal Languages & Automata 4th by Peter Linz.

Section 7.1

3. Construct npda’s that accept the following regular languages:

a) L1 = L(aaa*b)

7.1.3a solution

A npda that accepts a regular language doesn’t need a stack because the language can be handled by a finite automaton, so we create a npda that simply doesn’t care about the stack.

4. Construct npda’s that accept the following languages on ? = {a, b, c}.

c) L = {anbmcn+m : n ³ 0, m ³ 0}

Here we need the stack.  We need to do two things: make sure the symbols come in the correct order and make sure the number of c’s is correct.  The order is taken care of by the transitions from state to state.  The number of c’s is taken care of by pushing a symbol for each a or b and popping for each c and requiring that the stack winds up with only the start symbol.


h)      L = {na(w) = 2nb(w)}

In this case we don’t care about the order.  We just need to make sure that the number of a’s is twice the number of b’s.  This is actually tricky.  The idea is to push two symbols for each b and pop one symbol for each a.  Conversely, we could push one symbol for each a and pop two symbols for each b.  The problem is best understood by considering aab, baa, and aba.  It all depends on what the first symbol is.  If the first symbol is a b then we merely push two symbols onto the stack and wait until they can both be popped off by seeing two a’s.  If the first symbol is an a then we would need to push a symbol for the a and hope that we later on see another a allowing us to pop off two symbols when we encounter the b.  But what if we see a b before we see the next a (this is the aba example in its simplest form)?  There aren’t two symbols on the stack to pop off.

7.1.4h solution