Bissoy.com
Doctors Medicines MCQs Q&A

Which of the following problems are decidable? 1) Does a given program ever produce an output? 2) If L is a context-free language, then, is L̅  also context-free? 3) If L is a regular language, then, is L̅  also regular? 4) If L is a recursive language, then, is L̅  also recursive? 

Which of the following problems are decidable? 1) Does a given program ever produce an output? 2) If L is a context-free language, then, is L̅  also context-free? 3) If L is a regular language, then, is L̅  also regular? 4) If L is a recursive language, then, is L̅  also recursive?  Correct Answer 3, 4

The correct answer is option 4

CONCEPT:

Decidable language: A language is decidable if there exists a Turing machine which halts or accepts it.

EXPLANATION:

1: Undecidable

There is no TM to determine whether a given program will produce an output.

2: Undecidable

Context-free languages are not closed under complementation.

3: Decidable

Regular languages are closed under complementation.

4: Decidable

Recursive languages are closed under complementation.

So option 4 is correct

Related Questions

Consider the following statements. I. The complement of every Turing decidable language is Turing decidable II. There exists some language which is in NP but is not Turing decidable III. If L is a language in NP, L is Turing decidable Which of the above statements is/are true?
Consider three software items: Program-X, Control Flow Diagram of Program-Y and Control Flow Diagram of Program-Z as shown below Program-X: Control Flow Diagram of Program-Y sumcal (int maxint, int value) {       int result=0, i=0;       if (value <0)       {           Value = -value;       }       while ( (i
In a village 50% of the villagers produce rice, 40% of the villagers produce apples and 50% of the villagers produce vegetables, 20% of the villagers produce rice and apples both, 25% of the villagers produce apples and vegetables both, 20% of the villagers produce rice and vegetables both and 10% of the villagers produce all three. Find the percentage of villagers who do not produce anything.
Which of the following statements about Regular Expression is/are incorrect? A. The union of two regular expressions is also a regular expression B. The concatenation of two regular expressions is also a regular expression C. The iteration of a regular expression is also a regular expression
At an Electronic Data processing unit, five out of the eight program sets P,Q,R,S,T,U,V and W are to be operated daily. On any one day, except for the first day of a month, only three of the program sets must be the ones that were operated on the previous day. The program operating must also satisfy the following conditions: 1. If program P is to be operated on a day, V can’t be operated on that day. 2. If Q is to be operated on a day, T must be one of the programs to be operated after Q. 3. If R is to be operated on a day, V must be one of the programs to be operated after R. 4. The last program to be operated on any day must be either S or U. If the program sets R and W are to be operated on the first day, which of the following could be the other program on that day?
Read the passage carefully and choose thebest answer to each question out of the four alternativesand click the button corresponding to it. To know language is to be able to speak it; even a childwho does not yet attend school can speak his or herlanguage. In order to speak a language it is important tolisten to it and to read a few pages in it everyday. A childpicks up language and learns to talk just as (s)he learnsto walk. Walking and talking comes naturally to a child asit grows. In our country, a child may grow up speakingmore than one language, if these languages are spoken inthe home and in the neighbourhood. we call thismultilingualism. A child speaks a language or languagesmuch before (s)he starts going to school. To know alanguage then is first of all to be able to speak it as easilyand naturally as a tree year old child does. Later on thechild will learn to read and write in that language. In orderto read and write in a language, one has to speak it. But itis possible to speak a language but not able to read orwrite in it. A baby does not speak until it is nine monthsold but it understands a few words at six months of age.It has been listening ever since it was born, and even alittle before that. So the first strategy in speaking alanguage is to listen. A child has been __________ ever since it was born
Read the passage carefully and choose thebest answer to each question out of the four alternativesand click the button corresponding to it. To know language is to be able to speak it; even a childwho does not yet attend school can speak his or herlanguage. In order to speak a language it is important tolisten to it and to read a few pages in it everyday. A childpicks up language and learns to talk just as (s)he learnsto walk. Walking and talking comes naturally to a child asit grows. In our country, a child may grow up speakingmore than one language, if these languages are spoken inthe home and in the neighbourhood. we call this multilingualism. A child speaks a language or languagesmuch before (s)he starts going to school. To know alanguage then is first of all to be able to speak it as easilyand naturally as a tree year old child does. Later on thechild will learn to read and write in that language. In orderto read and write in a language, one has to speak it. But itis possible to speak a language but not able to read orwrite in it. A baby does not speak until it is nine monthsold but it understands a few words at six months of age.It has been listening ever since it was born, and even alittle before that. So the first strategy in speaking alanguage is to listen. It is necessary for one to __________ the language before(s)he writes in that language.
Which of the following problems are decidable? I. Checking whether two regular languages are equivalent languages II. Checking whether two non-deterministic finite automata accept the same language III. Checking whether two context free grammars generate equivalent languages  IV. Checking whether a language of a context free grammar is non-empty
Read the passage carefully and choose thebest answer to each question out of the four alternativesand click the button corresponding to it. To know language is to be able to speak it; even a childwho does not yet attend school can speak his or herlanguage. In order to speak a language it is important tolisten to it and to read a few pages in it everyday. A childpicks up language and learns to talk just as (s)he learnsto walk. Walking and talking comes naturally to a child asit grows. In our country, a child may grow up speakingmore than one language, if these languages are spoken inthe home and in the neighbourhood. we call thismultilingualism. A child speaks a language or languagesmuch before (s)he starts going to school. To know alanguage then is first of all to be able to speak it as easilyand naturally as a tree year old child does. Later on thechild will learn to read and write in that language. In orderto read and write in a language, one has to speak it. But itis possible to speak a language but not able to read orwrite in it. A baby does not speak until it is nine monthsold but it understands a few words at six months of age.It has been listening ever since it was born, and even alittle before that. So the first strategy in speaking alanguage is to listen. To know a language one must be able to?
Imagine, you are solving a classification problems with highly imbalanced class. The majority class is observed 99% of times in the training data. Your model has 99% accuracy after taking the predictions on test data. Which of the following is true in such a case?
1. Accuracy metric is not a good idea for imbalanced class problems.
2.Accuracy metric is a good idea for imbalanced class problems.
3.Precision and recall metrics are good for imbalanced class problems.
4.Precision and recall metrics aren't good for imbalanced class problems.