Turing Machine.

2. [20 points| Consider the language AEcFG -(G) : G is a CFG that generates ?} . A trivial way to show that ACFG is decidable is to run the TM for ACFG to see whether ?G. ?? ? AcFG. Instead, show that AECFG is decidable by exhibiting a direct algorithm for it (that doesn't involve converting G to Chomsky normal form). You should find some inspiration for this by reviewing the algorithm for EcpG