# 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) *L*_{1} = *L*(*aaa*b*)

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* = {*a ^{n}b^{m}c^{n}*

^{+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* = {*n _{a}*(

*w*) = 2

*n*(

_{b}*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.