Bissoy.com
Doctors Medicines MCQs Q&A

Consider the following two statements about regular languages: S1: Every infinite regular language contains an undecidable language as a subset. S2: Every finite language is regular. Which one of the following choices is correct?

Consider the following two statements about regular languages: S1: Every infinite regular language contains an undecidable language as a subset. S2: Every finite language is regular. Which one of the following choices is correct? Correct Answer Both S<span style="position: relative; line-height: 0; vertical-align: baseline; bottom: -0.25em;font-size:10.5px;">1</span> and S<span style="font-size: 10.5px;">2</span> are true.

Key Points

note that the following statements are true

  1. Every infinite regular language L has a subset S which is undecidable. 
  2. Every infinite regular language L has a subset S which is unrecognizable.
  3. Every infinite language L has a subset S which is undecidable.
  4. Every infinite language L has a subset S which is unrecognizable.

So, S1 and S2 both are correct.  

the correct answer is option 4

Explanation: for statements S2 consider the following explanation

every infinite language (regular or not) has an undecidable subset.

With the particular focus on regular languages, the intended solution might have been something like using the pumping lemma to find x,y,z such that xynz is in your language for every n,  then consider the subset A = {xynz | n ∈ N}, where A is your favorite undecidable set of natural numbers.

it proves s1 is correct.

Related Questions

Consider the following relation on subsets of the set ? of integers between 1 and 2014. For two distinct subsets U and V of S we say U < V if the minimum element in the symmetric difference of the two sets is in U. Consider the following two statements: S1: There is a subset of S that is larger than every other subset. S2: There is a subset of S that is smaller than every other subset. Which one of the following is CORRECT?
Which of the following statement(s) is/are TRUE? (i) The family of context-free languages are the proper subset of the family of regular languages. (ii) The family of recursive languages is a proper subset of the family of recursively enumerable languages.
Which of following problems are undecidable? I. Membership problem in context-free languages II. Whether a given context-free language is regular III. Whether a finite state automation halts on all inputs IV. Membership problem for type 0 languages
In the following question, two statements are given each followed by two conclusions I and II. You have to consider the statements to be true even ifthey seem to be at variance from commonly known facts. You have to decide which of the given conclusions, if any, follows from the given statements. Statements:
(I) Empty set is a subset of any set.
(II) A set is a subset of power set. Conclusion:
(I) Empty set is a power set.
(II) A set is a subset of power set.
Study the accompanying Venn diagram that represents groups of persons speaking five different languages as follows. Oblong circle = Marathi ; Rectangle = Kannada, Circle = English, Triangle = Gujarati, Equilateral quadrangle = Hindi Using above information select the false statement/s from following list. (a) Area c represent persons speaking 5 languages but area d represents persons speaking 4 languages only. (b) Areas b and d represent persons speaking same number of languages. (c) Areas f, b and e represent persons speaking same languages. (d) Areas g and h represent persons who speak two languages only. 
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
United Nations has declared the year 2019 as 'Indigenous Languages Year'. The purpose is : (a) To protect the Indigenous Languages in the world. (b) To create consciousness about decaying Indigenous Languages. (c) Resurrection of declining these languages. (d) To realise the contribution of these languages to the world cultural diversity. Which of the above purpose/purposes is/are correct ?
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
Consider the following statements. I. If L1 ∪ L2 is regular, then both L1 and L2 must be regular. II. The class of regular languages is closed under infinite union. Which of the above statements is/are TRUE?
A learner in a village in the state of Jharkhand knows her mother tongue and Hindi, the language of home and in her neighbourhood. She learns English in school. Which of the languages come under language acquisition and which of the languages come under language learning? I. Mother tongue and Hindi come under language acquisition II. English comes under language learning III. Hindi comes under language learning IV. All the three languages come under language acquisition