0 votes 0 votes Let $PREFIX-FREE_{REX} = \{\langle R \rangle \mid \text{R is a regular expression and L(R) is prefix-free}\}$. Show that $PREFIX FREE_{REX}$ is decidable. Why does a similar approach fail to show that $PREFIX-FREE_{CFG}$ is decidable? Theory of Computation michael-sipser theory-of-computation regular-expression decidability proof + – admin asked Oct 17, 2019 • edited Oct 17, 2019 by Lakshman Bhaiya admin 399 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.