Answered You can hire a professional tutor to get the answer.
1. Show that the following decision problem is decidable: Given a CFG G, is L(G) not empty?
1. Show that the following decision problem is decidable: Given a CFG G, is L(G) not empty?Think of a way to mark all variables A such that for some string x ∈ Σ*, A (⇒*(over)G) x. Explain the algorithm in detail.2. Consider the following problem ALLCFG: Given a CFG G, is L(G) = Σ*? This problem is undecidable. (You don’t have to prove this).(a) Is this problem in RE (the class of recursively enumerable languages), in coRE (the class of all languages whose complement is in RE), in both, or in neither? Explain your answer.(b) Use the undecidability of ALLCFG to show that the following problem is also undecidable:Given a PDA M1 and an FA M2, is L(M1) = L(M2)?
