Timeline for Are there any algorithms that decide if a PDA (pushdown automaton) accepts a sentence?
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 5, 2022 at 1:08 | comment | added | D.W.♦ | Yeah, this doesn't work, because the set of reachable configurations is typically infinite (thanks to $\epsilon$-transitions), but the basic idea can be made to work with more work -- see my answer for how. | |
| Jan 4, 2022 at 19:13 | history | edited | Nathaniel | CC BY-SA 4.0 |
added 166 characters in body
|
| Jan 4, 2022 at 19:11 | comment | added | Nathaniel | You are right! I unconsciously worked without $\varepsilon$-moves. | |
| Jan 4, 2022 at 15:59 | comment | added | Hendrik Jan | This is nontrivial if you need to deal with $\varepsilon$ rules that push, I think. The set of reachable configurations might be infinite. Unless there any bound on the stack height? | |
| Jan 4, 2022 at 15:52 | history | edited | Nathaniel | CC BY-SA 4.0 |
added 119 characters in body
|
| Jan 4, 2022 at 15:40 | history | answered | Nathaniel | CC BY-SA 4.0 |