Bissoy.com
Doctors Medicines MCQs Q&A

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

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 Correct Answer II and IV

Concept

A problem is said to be Decidable if we can always construct a corresponding algorithm that can answer the problem correctly. Based upon this property, problems are classified as

  1. Decidable
  2. Semi-decidable
  3. Undecidable

Explanation:

Statement i: Decidable

Membership problem in CFL is decidable using CYK algorithm to check the membership.

Statement ii: Undecidable

To check whether a given CFL is regular or not in undecidable.

Statement iii: Decidable

To determine whether an FA halts on all inputs or not is decidable because we have final and non-final states in FAs that indicate whether the input string is accepted or not.

Statement iv: Undecidable

Membership problem for type 0 (Recursively Enumerable) grammars is undecidable.

Related Questions

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
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?
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)?  
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
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:
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 problems. L(?) denotes the language generated by a grammar ?. L(?) denotes the language accepted by a machine ?. (I) For an unrestricted grammar ? and a string ?, whether ? ∈ (?) (II) Given a Turing machine M, whether L(M) is regular (III) Given two grammars ?1 and ?2, whether (?1) = (?2) (IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language. Which one of the following statements is correct?
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 nondeterministic finite automation with ε-moves is an extension of nondeterministic finite automation.
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?