Reduction from the post correspondence problem

Assignment Help Theory of Computation

Reference no: EM132709526

Question 1.Rigorously establish the decidability or undecidability of the following languages:

(a) L = {0n|the decimal expansion of π = 3.14 . . . contains n (or more) consecutive 0's}.

(b) L = {(D) | D is a DFA and L(D) is not recognized by a DFA with fewer states}.

Question 2. Prove that the following language is undecidable by giving a reduction from the Post Correspondence Problem.

L = {(G) | G is a CFG and L(G) contains at least one palindrome}.

Question 3. Let A be any language in P over the alphabet {0, 1}. Prove that LA = {1n | n ∈ N, A ∩ {0, 1}ⁿ ≠0} is in NP.

Reference no: EM132709526

Questions Cloud

Federal emergency management agency : Describe the mission of the Federal Emergency Management Agency (FEMA), and provide explanations and examples for each aspect of the mission.

Explain locke view of human nature : Explain Locke's view of human nature. Use details from the textbook to support your description. Explain Hobbes's view of human nature, again using details.

Find order quantity that will minimize total annual cost : A jewelry firm buys semiprecious stones to make bracelets and rings. The supplier quotes a price of $8.80 per stone for quantities of 600 stones or more

What are the five typical factors that lender will consider : What are the five typical factors that a lender will consider when evaluating a credit application? List and describe these five factors.

Reduction from the post correspondence problem : Prove that the following language is undecidable by giving a reduction from the Post Correspondence Problem

Discuss the role of biological triggers : Discuss the role of biological triggers in the role of psychological disorders. Choose one of the following disorders: Depression, Schizophrenia, or Alcoholism.

Modes of entry into foreign markets : Define the following modes of entry into foreign markets:

What are the political-cultural-environmental-economic : What are the political, cultural, environmental, economic, and trade risks present when doing business in the country as an outsider?

Describe the relationship between strategy and structure : Define corporate governance and explain why it is used to monitor and control top-level managers' decisions.

User Account

All Pages