2

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?

user314159
  • 127

2 Answers2

2

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.

MJD
  • 65,394
  • 39
  • 298
  • 580
  • I do not understand what you mean by counter? I am trying to describe these with $\delta$ functions. – user314159 Apr 10 '14 at 14:32
  • 1
    The finite state of the PDA can store a finite amount of information. A counter is a series of states, say $s_0, s_1, \ldots, s_n$, with $\delta(s_i, \mathtt{b}) = s_{i+1}$. The idea is that if the machine is in state $s_i$, that means it has counted $i$ b symbols. When the machine is in state $s_0$ it knows it has not seen any b symbols yet. When it is in state $s_1$, it knows it has seen one b symbol, because $\delta(s_0, \mathtt{b}) = s_1$. Similarly in state $s_2$ the machine knows it has seen two b symbols. To reset the counter simply means to return to state $s_0$. – MJD Apr 10 '14 at 14:43
  • 1
    @user314159 It is much easier to design machines by thinking of counters and variables than by thinking directly in terms of states. Once you have the design done, it is easy to implement the required counters and variables as machine states. For example, here is a machine that has two counters, one counting how many 0s and one counting how many 1s it has seen. The machine accepts the input if it has seen at least two 0s and at most two 1s. – MJD Apr 10 '14 at 14:46
  • I posted an answer below because it was too big for here, does that make sense? – user314159 Apr 10 '14 at 16:14
  • Also is $L_2 = {a^nb^mc^k \mid n = m : or : m \ne k}$ even a CFL? – user314159 Apr 10 '14 at 16:15
  • 1
    It is the union of ${a^nb^mc^k\mid n=m}$ and ${a^nb^mc^k\mid m\ne k}$, both of which are CFLs. – MJD Apr 10 '14 at 16:18
  • Ok that makes sense. So for the first part I have that $\delta(q_0,a,z)=(q_1,az)$; $\delta(q_0,\lambda,z)=(q_3,\lambda)$; $\delta(q_1,a,a)=(q_1,aa)$; $\delta(q_1,b,a)=(q_2,\lambda)$; $\delta(q_2,b,a)=(q_2,\lambda)$; $\delta(q_2,\lambda,z)=(q_3,\lambda)$. I think that works for the first half, but how do I approach it when $m \ne k$? – user314159 Apr 10 '14 at 18:26
  • 1
    ${a^nb^mc^k\mid m\ne k}$ is the union of ${a^nb^mc^k\mid m<k}$ and ${a^nb^mc^k\mid m>k}$. – MJD Apr 10 '14 at 21:21
  • So for {$a^nb^mc^k | m<k$} it would be $\delta(q_0,b,z)=(q_1,bz)$; $\delta(q_1,b,b)=(q_1,bb)$; $\delta(q_1,c,b)=(q_2,\lambda)$; $\delta(q_2,c,b)=(q_2,\lambda)$; $\delta(q_2,c,z)=(q_3,z)$; $\delta(q_3,c,z)=(q_3,z)$?

    Is that right?

     – user314159 Apr 11 '14 at 01:02
1

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?

user314159
  • 127