FLAT UNIT 5

Which of the following technique is used to find whether a natural language isn't recursive enumerable?

• Diagonalization

• Recursive Induction

• All of the mentioned

• None of the mentioned

Diagonalization can be useful in:

• To find a non-recursively enumerable language

• To prove undecidability of halting problem

• To find a non-recursively enumerable language & also proves undecidability of halting problem

• None of the mentioned

Which of the following are undecidable problems?

• Determining whether two grammars generate the same language

• Determining whether a grammar is ambiguous

• Determining whether a grammar is ambiguous and two grammars generate the same language

• None of the mentioned

Which of the following are incorrect options?

• Informally, problem is a yes/no question about an infinite set of possible instances

• Formally, a problem is a language

• All of the mentioned

• None of the mentioned

If a problem has an algorithm to answer it, we call it _________

• decidable

• solved

• recognizable

• none of the mentioned

Which of the following are decidable problems?

• Can a particular line of code in a program ever be executed?

• Do two given CFG's generate the same language

• Is a given CFG ambiguous?

• None of the mentioned

Which one of the following is true for the given? A={(M,w)|M is a Turing machine that accepts string w}

• A concrete undecidable problem

• A is recognizable but not decidable

• -A is not recognizable

• All of the mentioned

Which of the following are correct statements?

• TMs that always halt are known as Decidable problems

• TMs are not guaranteed to halt only on acceptance are recursive enumerable

• All of the mentioned

• None of the mentioned

Statement: If L id R.E., Lc needs to be R.E. Is it correct?

• Yes

• No

• Maybe

• Cannot predict

Which of the following is true for The Halting problem?

• It is recursively enumerable

• It is undecidable

• It is recursively enumerable and undecidable

• None of the mentioned