2
$\begingroup$

I'm trying to understand the approach to constructing a PDA which accepts the language { $a^i b^j c^k \mid i,j,k \geq0, i+2k = j$ }

$\endgroup$
  • $\begingroup$ Are you able to write automatons for just $\{ a^i b^j c^k \mid i,j,k \geq0, i+2k = j \}$ and just $a^3b^7c^2$? $\endgroup$ – Karolis Juodelė Mar 6 '13 at 15:20
  • 1
    $\begingroup$ Your question is weird. For constructing a PDA you need no instance of a string, just the whole language. So if you want to be understood you should ask two questions: (a) how do I construct a PDA for $\lbrace a^i b^j c^k \mid i, j, k \geq 0, i + 2 k = j\rbrace$, and (b) how does the PDA work to accept the string $a^3 b^7 c^2$? $\endgroup$ – Andrej Bauer Mar 6 '13 at 15:21
  • 3
    $\begingroup$ Notice that $a^ib^jc^k=a^ib^{i+2k}c^k=a^ib^ib^{2k}c^k=$. $\endgroup$ – mrk Mar 6 '13 at 15:21
  • $\begingroup$ @AndrejBauer I think he means crafting the PDA and matching the string. I might be wrong. $\endgroup$ – mrk Mar 6 '13 at 15:24
  • 1
    $\begingroup$ Carelessly didn't realized it was part of the language, so i fixed it to one question, but yeah Andrej, that's exactly what I meant $\endgroup$ – Iancovici Mar 6 '13 at 15:26
6
$\begingroup$

Your language is equivalent to the language $a^ib^ib^{2k}c^k$, and since concatenation is associative, this is equivalent to $(a^ib^i)(b^{2k}c^k)$.

A PDA for the first of these parts pushes an $a$ for each $a$ it sees and pops an $a$ when it sees a $b$. If the topmost stack symbol after this is $Z_0$, transition to the second PDA, which pushes a $b$ for every two $b$s it sees and then pops a $b$ for every $c$ it sees, accepting if, after this, you end up with no input and $Z_0$ as the topmost symbol.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ what about PDA for $a^ib^jc^k \mid i + j =k$ how can you count a's and b's and execute c's enough so it is accepted. must the stack be empty for the pda to accept the language? One grammar for that could be $A \rightarrow aAc \mid B \mid \epsilon,$ $B \rightarrow bBc \mid \epsilon$ $\endgroup$ – Iancovici Mar 12 '13 at 18:52
  • $\begingroup$ @echadromani 1. Add an $a$ to the stack for every $a$ you read. 2. Add a $b$ to the stack for every $b$ you read. 3. Remove the top stack symbol for each $c$ you read. 4. Accept if the stack is empty and you have no more input. Reject if you crash or run out of input without emptying the stack. $\endgroup$ – Patrick87 Mar 12 '13 at 19:36
  • $\begingroup$ 1 how exactly do you accept if the stack is empty, 2 and remove the top stack symbol for each c? $c, a/\epsilon$ $c, b/\epsilon$? $\endgroup$ – Iancovici Mar 12 '13 at 19:46
  • $\begingroup$ @echadromani 1 If the topmost stack symbol is the special bottom-of-stack symbol (I've usually seen this represented as $Z_0$), transition to a new state. Any subsequent input either crashes or takes you to a dead state. Only if the input stops there do you accept. 2. Yes, you have the two transitions you mention. $\endgroup$ – Patrick87 Mar 12 '13 at 20:00
  • $\begingroup$ I'm new to the PDA, at the state in which those two transitions are available, do we assume it won't try to perform $c, a/ \epsilon$ while $b$ is at the top of the stack? $\endgroup$ – Iancovici Mar 13 '13 at 11:25
6
$\begingroup$

Hint: The PDA has three phases: an $a$ phase, a $b$ phase and a $c$ phase. Your goal in the $a$ phase is to "compute" $i$ by strong an appropriate load on the stack. Your goal in the $b$ phase is to compute $j-i$. Finally, your goal in the $c$ phase is to compare $j-i$ to $2k$.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

Hint: find a PDA for the language $\{a^kb^k:k\ge 0\}$ and apply it twice.

The other approach is to find a grammar for the language and convert it to an equivalent PDA. Here is the grammar version:

$S \to AB \mid \epsilon$

$A \to aAb \mid ab$

$B \to bbBc \mid bbc$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

I think the best solution would be to form the CFG first and convert it to the equivalent PDA. the CFG can be constructed as follows: there are 2 cases:
1> an a for a b
2> a c for 2 b's

so when you add up, you make it equalized.

i.e.,
S -> AB
A -> aAb / epsilon
B -> bbBc / epsilon

| cite | improve this answer | |
$\endgroup$

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.