Timeline for Are there any algorithms that decide if a PDA (pushdown automaton) accepts a sentence?
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 14 at 8:33 | comment | added | bobismijnnaam | @JerryDing Re: example on page 17, I agree. The edge p -n4> accept cannot be constructed. I think this is clear from the phase 2 saturation rules: rule 1 cannot have caused it, as it can only be applied to epsilon rules. Rule 3 cannot have caused it, as it only adds edges to auxiliary nodes (e.g. the node p_e_f). Then rule 2 must have added it. But there is no rule with only n4 on its right hand side! So n4 also cannot be added by rule 2. The rest of the example looks as I would expect. | |
| Mar 9 at 7:57 | comment | added | D.W.♦ | @JerryDing, I don't know, but that sounds like a question worth asking separately (you can use the 'Ask Question' button to ask - include full context to make the question self-contained). | |
| Mar 9 at 7:52 | comment | added | Jerry Ding | I'm trying to follow the algorithm for $\mathrm{post^*}(C)$ given in the book, on page 17 they show an example for the ICFG program on page 14. The algorithm is not described clearly and I cannot understand why there is a transition from state $p$ to the accepting state using stack symbol $n_4$. I can only make a epsilon transition from $p$ to $p_{ef}$, which then has a transition to the accepting state using symbol $n_4$. Also the $\mathrm{pre^*}(C)$ seems too simple, I cannot derive that $e_{main}$ is backward reachable from $x_{main}$. What could I be misunderstanding? | |
| Oct 11, 2023 at 4:55 | comment | added | D.W.♦ | @Electro, yes, that's correct. | |
| Oct 11, 2023 at 4:51 | comment | added | Electro | So, if I understand this correctly, we are essentially building the input $x$ into the PDA $P$ to convert it into an almost-PDS $Q$. Since any accepting path in $Q$ corresponds to reading in exactly the input, it follows that $P$ accepts $x$ iff $Q$ accepts anything. That is, all we need to do is check whether $L(Q)$ is empty. To do this, we turn $Q$ into a PDS $R$ by deleting the input component of each transition, and then check whether $R$ can reach any of $Q$'s accept states after being started in $Q$'s start state with an empty stack. | |
| Oct 4, 2023 at 17:57 | history | edited | D.W.♦ | CC BY-SA 4.0 |
Update links to where it can be downloaded. The original link is broken.
|
| S Oct 4, 2023 at 17:40 | history | suggested | Electro | CC BY-SA 4.0 |
Reference should be to section 2.2.2; 2.2.3 is the number of the definition
|
| Oct 4, 2023 at 17:32 | comment | added | D.W.♦ | @Electro, that is explained in the paragraph beginning "Now, given an input word ...". $Q$ can be viewed as a PDS. $\text{post}^*(Q)$ contains an accepting configuration iff $x \in L(P)$. | |
| Oct 4, 2023 at 13:12 | comment | added | Electro | The mentioned article and its citations seem to discuss only "pushdown systems" (PDSs), which don't have an input that they accept/reject. How does one go from these results on PDSs to PDAs? | |
| Oct 4, 2023 at 12:46 | review | Suggested edits | |||
| S Oct 4, 2023 at 17:40 | |||||
| Jan 5, 2022 at 1:07 | history | answered | D.W.♦ | CC BY-SA 4.0 |