Pushdown Automata

Question

I having trouble constructing NPDAs for these two languages:

$L_1 = \{a^nb^m \mid 2n \le m \le 3n\}$

$L_2 = \{a^nb^mc^k \mid n = m \: or \: m \ne k\}$

Would these be the proper states for the first one?

• $q_0$ – reading $a$’s (initial state)
• $q_1$ – reading $b$’s and popping $A$’s
• $q_2$ – reading $b$’s
• $q_f$ – final state

Would these be the proper states for the second one?

• $q_0$ – reading $a$’s (initial state)
• $q_1$ – reading $b$’s and popping $A$’s
• $q_2$ – reading $b$’s and pushing $B$’s
• $q_3$ – reading $c$’s
• $q_f$ – final state

I do not think I am approaching this properly. This is not non deterministic right? How should I do this?

Answer 1

Hint for (a): I think you need more states than you said. Here's my idea.

Every time the machine reads an a, it should push a token on the stack. Eventually there will be $n$ tokens on the stack.

When the machine starts seeing bs it should use its finite control to keep count of how many it has seen. After it reads 2 bs, it should nondeterministically decide between:

1. reading one more b, then resetting the counter to 0 and popping a token from the stack, or
2. resetting the counter and popping the stack without reading another b.

The computation that chooses (1) every time will empty the stack after reading exactly $3n$ bs; the computation that chooses (2) every time will empty the stack after reading exactly $2n$ bs; a computation that chooses some of each will empty the stack after reading some intermediate number of bs. So if the number of bs is in the right range, some computation will make the right sequence of choices and empty the stack just as the input ends.

Answer 2

I think I am beginning to understand this. I do not know how to do a diagram on here so this description might be a little rough:

$\rightarrow q_0$$\rightarrow (a,0,11)$$\rightarrow q_1 $$\rightarrow (b,11,\lambda) \: and \: (b,111,\lambda)$$\rightarrow q_2$$\rightarrow (\lambda,0,\lambda)$$\rightarrow q_3$

with $q_1 \rightarrow (a,1,11) \rightarrow q_1$

and $q_2 \rightarrow (b,11,\lambda) \: and \: (b,111, \lambda) \rightarrow q_2$

So the delta functions would be: $\delta(q_0,a,0) = (q_1,10)$; $\delta(q_0,\lambda,0) = (q_3,\lambda)$; $\delta(q_1,a,1) = (q_1,11)$; $\delta(q_1,b,11) = (q_2,\lambda)$; $\delta(q_1,b,111) = (q_2,\lambda)$; $\delta(q_2,b,11) = (q_2,\lambda)$; $\delta(q_2,b,111) = (q_2,\lambda)$; $\delta(q_1,b,11) = (q_2,\lambda)$; $\delta(q_2,\lambda,0) = (q_3,\lambda)$;

Does this make sense?