Rigorously establish the decidability or undecidability of the following languages: (a) (20 Points) L = 0 n . (b) (20 Points) L = D is a DFA and L(D) is not recognized by a DFA with fewer states. 2. (30 Points) Prove that the following language is undecidable by giving a reduction from the Post Correspondence Problem. L = hGi . 3. (30 Points) Let A be any language in P over the alphabet 0, 1. Prove that LA = 1 n
Our customer support team is here to answer your questions. Ask us anything!
👋 How can we help with you?