I've been studying Computation Theory, and in an exercise I am asked to construct a PDA that accepts the language $L=\{x\in(a,b), \#_a(x) = 2\#_b(x)\}$, where $x$ is the input string and $\#_a(x),\#_b(x)$ the number that $a$ or $b$ appears in the $x$ string.

That means that the following sequences should all be accepted:

aab aba bbaabaaaa baabaa abbaaa

My problem: I've found examples of PDAs being constructed for $a^nb^n$ and even $a^{2n}b^n$ which is pretty close to what I'm looking for, but these languages all have a predetermined sequence of the $a$s coming first, then the $b$s.

I've been trying for literally hours to build a PDA that circles between how many $a$s and $b$s it has, and how many it still needs, but every attempted solution has been wrong (situations where consequent same letters cause pops on empty stacks, halting the PDA).

Any information or methodical approaches on constructing a PDA out of a language like that? I'm at my wit's end.

  • $\begingroup$ Hint only for now: if you have $a$ you push $a$, if you have second $a$, you push $A$. So how about negative number of $a$ if you start from $b$? $\endgroup$
    – Evil
    Sep 12 '15 at 19:12
  • $\begingroup$ @EvilJS You mean b popping $a$ or $A$? What's the point of $b$ inserting negative values if you can only push or pop? $\endgroup$ Sep 12 '15 at 19:51
  • $\begingroup$ You have to remember how many $a$'s or $b$'s you have. Encode it in terms of $a$. $b$ is not popping $a$ but is popping $A$. If you have $b$ and then add $a$ you are expecting another $a$ to make it even. $a$ = 0.5, $A$ = 1, $b$ = -1, do you follow? $\endgroup$
    – Evil
    Sep 12 '15 at 19:57
  • $\begingroup$ I've been trying to solve it like this, yes, always measuring how many $a$s and $b$s I have, then expecting the appropriate number of elements. But I always end up in situations of a state popping the stack, encountering an unexpecting value and halting. A PDA halts when popping the wrong value, right? $\endgroup$ Sep 12 '15 at 20:06
  • 1
    $\begingroup$ @DimitrisSfounis stack alphabet must be a finite set. $\endgroup$ Sep 13 '15 at 14:58

GPDA$\to$PDA Approach

See you have got a solution from chat. But the first thing popped my mind is a Generalized_pushdown_automaton(GPDA), which can be constructed pretty straight forward.

GPDA construction

$M=(Q,\Sigma,\Gamma,\delta,q_0,Z,\{q_f\})$, where $Q=\{q_0,q_f\},\Sigma=\{a,b\},\Gamma=\{a,A,Z\}$,$\delta$ includes following rules:

  1. $(q_0,a,Z)\to(q_0,aZ)$
  2. $(q_0,b,Z)\to(q_0,AAZ)$
  3. $(q_0,a,a)\to(q_0,aa)$
  4. $(q_0,b,A)\to(q_0,AAA)$
  5. $(q_0,a,A)\to(q_0,\epsilon)$
  6. $(q_0,b,aa)\to(q_0,\epsilon)$
  7. $(q_0,b,aZ)\to(q_0,AZ)$
  8. $(q_0,\epsilon,Z)\to(q_f,\epsilon)$

GPDA$\to$PDA convertion

Using the algorithm provided on Wikipedia, we can convert it to PDA easily. Only 6. and 7. need to convert:

6.1 $(q_0,b,a)\to(p_0,\epsilon)$

6.2 $(p_0,\epsilon,a)\to(q_0,\epsilon)$

7.2 $(p_0,\epsilon,Z)\to(q_0,AZ)$

Resulting PDA is $M=(Q',\Sigma,\Gamma,\delta',q_0,Z,\{q_f\})$ where $Q'=\{q_0,p_0,q_f\}$ and $\delta'=(\delta\setminus\{6,7\})\cup\{6.1,6.2,7.2\}$. The constructed PDA is non-deterministic.

Convert to DPDA

To convert to DPDA, the only affected transitions are 1. 2. and 8 in above rules:

$M=(Q,\Sigma,\Gamma,\delta,q_0,Z,\{q_f\})$, where $Q=\{q_0,p_0,q_f\},\Sigma=\{a,b\},\Gamma=\{a,A,Z\}$,$\delta$ includes following rules:

  1. $\mathbf{(q_0,\epsilon,Z)\to(q_f,Z)}$
  2. $(q_0,a,a)\to(q_0,aa)$
  3. $(q_0,b,A)\to(q_0,AAA)$
  4. $(q_0,a,A)\to(q_0,\epsilon)$
  5. $(q_0,b,a)\to(p_0,\epsilon)$
  6. $(p_0,\epsilon,a)\to(q_0,\epsilon)$
  7. $(p_0,\epsilon,Z)\to(q_0,AZ)$
  8. $\mathbf{(q_f,a,Z)\to(q_0,aZ)}$
  9. $\mathbf{(q_f,b,Z)\to(q_0,AAZ)}$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.