State true or false:Statement: The difference between PCP and MPCP is that in MPCP, a solution is required to start with the first string on each list.(a) Statement: The difference between PCP and MPCP is that in MPCP, a solution is required to start with the first string on each list.(b) true(c) falseThis question was posed to me by my college director while I was bunking the class.My enquiry is from Rice’s Theorem, Properties and PCP topic in section Undecidability of Automata Theory

State true or false:Statement: The difference between PCP and MPCP is

1.	State true or false:Statement: The difference between PCP and MPCP is that in MPCP, a solution is required to start with the first string on each list.(a) Statement: The difference between PCP and MPCP is that in MPCP, a solution is required to start with the first string on each list.(b) true(c) falseThis question was posed to me by my college director while I was bunking the class.My enquiry is from Rice’s Theorem, Properties and PCP topic in section Undecidability of Automata Theory
Answer» The CORRECT OPTION is (a) Statement: The difference between PCP and MPCP is that in MPCP, a solution is required to start with the first STRING on each list. The best explanation: The MPCP is : GIVEN lists A and B of K strings ,say A = w1 ,w2, …wk and B= x1, x2,…..xk does there exists a sequence of integers i1,i2,…ir such that w1wi1wi2…..WIR = x1xi1xi2…xir?

Discussion

No Comment Found

Related InterviewSolutions

The class of recursive language is known as:(a) R(b) RC(c) RL(d) All of the mentionedThis question was posed to me in a national level competition.This question is from The Universal Language-Undecidability topic in section Undecidability of Automata Theory
Decidable can be taken as a synonym to:(a) recursive(b) non recursive(c) recognizable(d) none of the mentionedThe question was asked in a job interview.I'd like to ask this question from The Universal Language-Undecidability topic in section Undecidability of Automata Theory
The language accepted by a turing machine is called ____________(a) Recursive Ennumerable(b) Recursive(c) Both (a) and (b)(d) None of the mentionedThe question was posed to me in an interview for job.Question is taken from The Universal Language-Undecidability topic in division Undecidability of Automata Theory
Which among the following are semi decidable?(a) Empty-DFA(b) Rec-NFA(c) Infinite-DFA(d) All of the mentionedI got this question in an internship interview.I would like to ask this question from The Universal Language-Undecidability topic in chapter Undecidability of Automata Theory
Which of the following technique is used to find whether a natural language isnt recursive ennumerable?(a) Diagonalization(b) Recursive Induction(c) Both (a) and (b)(d) None of the mentionedThe question was asked during an interview for a job.This intriguing question originated from The Diagonalization Languages topic in chapter Undecidability of Automata Theory
Recursive languages are also known as:(a) decidable(b) undecidable(c) sometimes decidable(d) none of the mentionedI have been asked this question by my school teacher while I was bunking the class.This question is from The Universal Language-Undecidability in section Undecidability of Automata Theory
Which of the following are incorrect options?(a) Informally, problem is a yes/no question about an infinite set of possible instances(b) Formally, a problem is a language(c) Both (a) and (b)(d) None of the mentionedThis question was addressed to me during an online interview.My question is taken from The Diagonalization Languages in division Undecidability of Automata Theory
A formal language is recursive if :(a) a total turing machine exists(b) a turing machine that halts for every input(c) turing machine rejects if the input does not belong to the language(d) all of the mentionedThe question was asked during an interview for a job.The origin of the question is The Universal Language-Undecidability in chapter Undecidability of Automata Theory
A problem is called __________ if its has an efficient algorithm for itself.(a) tractable(b) intractable(c) computational(d) none of the mentionedI have been asked this question in an interview.This intriguing question comes from The Universal Language-Undecidability topic in portion Undecidability of Automata Theory
If a problem has an algorithm to answer it, we call it _________(a) decidable(b) solved(c) recognizable(d) none of the mentionedThis question was posed to me in homework.My query is from The Diagonalization Languages in section Undecidability of Automata Theory

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment