retagged by
446 views
0 votes
0 votes

Prove that the following two languages are undecidable.

  1. $OVERLAP_{CFG} = \{\langle G, H\rangle \mid \text{G and H are CFGs where}\: L(G) \cap L(H) \neq  \emptyset\}$.
  2. $PREFIX-FREE_{CFG} = \{\langle G \rangle \mid \text{G is a CFG where L(G) is prefix-free}\}$.
retagged by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
1
admin asked Oct 20, 2019
694 views
Let $X = \{\langle M, w \rangle \mid \text{M is a single-tape TM that never modifies the portion of the tape that contains the input $w$ } \}$Is $X$ decidable? Prove you...