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$ }
$\begingroup$ $\endgroup$
5 
- $\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ė– Karolis Juodelė2013-03-06 15:20:00 +00:00Commented Mar 6, 2013 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– Andrej Bauer2013-03-06 15:21:14 +00:00Commented Mar 6, 2013 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– mrk2013-03-06 15:21:25 +00:00Commented Mar 6, 2013 at 15:21
- $\begingroup$ @AndrejBauer I think he means crafting the PDA and matching the string. I might be wrong. $\endgroup$mrk– mrk2013-03-06 15:24:17 +00:00Commented Mar 6, 2013 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– Iancovici2013-03-06 15:26:48 +00:00Commented Mar 6, 2013 at 15:26
Add a comment |
4 Answers
$\begingroup$ $\endgroup$
6 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.
- $\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– Iancovici2013-03-12 18:52:04 +00:00Commented Mar 12, 2013 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– Patrick872013-03-12 19:36:52 +00:00Commented Mar 12, 2013 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– Iancovici2013-03-12 19:46:47 +00:00Commented Mar 12, 2013 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– Patrick872013-03-12 20:00:28 +00:00Commented Mar 12, 2013 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– Iancovici2013-03-13 11:25:25 +00:00Commented Mar 13, 2013 at 11:25
$\begingroup$ $\endgroup$
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$.
$\begingroup$ $\endgroup$
0 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$
$\begingroup$ $\endgroup$
0 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
