Bissoy.com
Doctors Medicines MCQs Q&A

Given below are two statements: Statement I: The problem "Is L1 ∧ L2 = ϕ?" is undecidable for context sensitive languages L1 and L2. Statement II: The problem "Is WϵL?" is decidable for context sensitive language L, (where W is a string). In the light of the above statements, choose the correct answer from the options given below

Given below are two statements: Statement I: The problem "Is L1 ∧ L2 = ϕ?" is undecidable for context sensitive languages L1 and L2. Statement II: The problem "Is WϵL?" is decidable for context sensitive language L, (where W is a string). In the light of the above statements, choose the correct answer from the options given below Correct Answer Both Statement I and Statement II are true

The correct answer is option 1.

Key Points

  • The problem "Is L1 ∧ L2 = ϕ?" is undecidable for context-sensitive languages L1 and L2. Here L1∧ L2 is a disjoint operator it's undecidable problem.

Hence statement I is correct.

  • The problem "Is WϵL?" is decidable for context-sensitive language L, (where W is a string). Here W is a string that is accepted by the particular language is a membership problem and its decidable problem.

Hence statement II is correct.

Additional Information

Context-sensitive language is accepted by linear bounded automata and only membership(WϵL) problems are decidable.

Context-free language is accepted by pushdown automata and only membership problems(WϵL), finiteness L=finite, emptiness L=Φ are decidable.

Related Questions

For any two languages L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true? I. L̅1 (complement of L1) is recursive II. L̅2 (complement of L2) is recursive III. L̅1 is context-free IV. L̅1 ∪ L2 is recursively enumerable
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?
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
Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT? I. L1 ∪ L2 is context-free II. L̅1 is context-free III. L1 – R is context-free IV. L1 ∩ L2 is context-free
Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. Which of the following decision problems are undecidable? I. Given a regular expression R and a string w, is w ∈ L(R)? II. Given a context-free grammar G, is L(G) = ϕ? III. Given a context-free grammar G, is L(G) = ∑* for some alphabet ∑? IV. Given a Turing machine M and a string w, is w ∈ L(M)?  
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
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. 
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.
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
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?