0 votes 0 votes A useless state in a pushdown automaton is never entered on any input string. Consider the problem of determining whether a pushdown automaton has any useless states. Formulate this problem as a language and show that it is decidable. Theory of Computation michael-sipser theory-of-computation pushdown-automata decidability proof + – admin asked Oct 17, 2019 admin 505 views answer comment Share Follow See 1 comment See all 1 1 comment reply Joey commented Aug 6, 2020 reply Follow Share Wouldn't a simple directed graph representation of the states of the PDA along with the transitions, and a DFS/BFS on that be sufficient? 0 votes 0 votes Please log in or register to add a comment.