Bissoy.com
Doctors Medicines MCQs Q&A

Let G1 and G2 be arbitrary context free languages and R an arbitrary regular language. Consider the following problems: (A) Is L(G1) = L(G2)? (B) Is L(G2) ≤ L(G1)? (C) Is L(G1) = R? Which of the problems are undecidable ? Choose the correct answer from the options given below:

Let G1 and G2 be arbitrary context free languages and R an arbitrary regular language. Consider the following problems: (A) Is L(G1) = L(G2)? (B) Is L(G2) ≤ L(G1)? (C) Is L(G1) = R? Which of the problems are undecidable ? Choose the correct answer from the options given below: Correct Answer (A), (B) and (C)

The correct answer is option 4.

Key Points

S.NO

 

FA

Regular

PDA

DCFL

PDA

CFL

LBA

CSL

Recursive

HTM

REL

TM
1

Membership  WεL

 D D D D D UD
2 Finiteness L= finite D D D UD UD UD
3 Equivalence  L1=L2 D D UD UD UD UD
4 Is L1⊆ L2 Subset Checking D UD UD UD UD UD
5 Emptiness L1=Φ D D D UD UD UD
6 Disjoint Operator is L1∩L2=Φ D UD UD UD UD UD
7 Is L= Σ* Totality D UD UD UD UD UD
8 Is L regular language D D UD UD UD UD
  
  • D   =decidable
  • UD=undecidable

According to the above table, rows 3,4, and 8 it's undecidable.
∴ Hence the correct answer is (A), (B) and (C).

Related Questions

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)?  
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
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
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?
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
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
Consider the following languages L1 = {ap | p is a prime number} L2 = {anbmc2m | n ≥ 0, m ≥ 0} L3 = {anbnc2n | n ≥ 0} L4 = {anbn | n ≥ 1} Which of the following are CORRECT? I. L1 is context-free but not regular. II. L2 is not context-free III. L3 is not context-free but recursive. IV. L4 is deterministic context-free
Let P be a regular language and Q be a context-free language such that Q ⊆ P. (For example, let P be the language represented by the regular expression p*q*and Q be |pnqn | n ϵ N}). Then which of the following is ALWAYS regular?
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? 
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.