For each language, if it is recognizable, describe a TM which recognizes it. If it is not recognizable, prove that it isn't, using a reduction from any of HALTSTM, x), ACCEPTSTM, x), EQUAL_TM(TM1, TM2), REG_TM(TM), EQUAL_CFG(CFG1, CFG2), ALL_CFG(CFG), and EMPTY_TM(TM) .
Let L5 = (< CFG, x > | There exists a regular expression shorter than x with the same language as CFG.}