adplus-dvertising
frame-decoration

Question

Which of the following are decidable?

I. Whether the intersection of two regular languages is infinite
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same language
IV. Whether a given grammar is context-free

a.

I and II

b.

I and IV

c.

II and III

d.

II and IV

Answer: (b).I and IV

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. Which of the following are decidable? I. Whether the intersection of two regular languages is infinite II. Whether a given context-free language is regular III. Whether two...

Similar Questions

Discover Related MCQs

Q. Which of the following problems is undecidable?

Q. Let < M > be the encoding of a Turing machine as a string over {0, 1}. Let L = { < M > |M is a Turing machine that accepts a string of length 2014 }. Then, L is

Q. Which of the following problems is undecidable?

Q. Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?

Q. Consider the following statements:

1. The complement of every Turning decidable
language is Turning decidable
2. There exists some language which is in NP
but is not Turing decidable
3. If L is a language in NP, L is Turing decidable

Which of the above statements is/are True?

Q. Let L={w ∈ (0 + 1)*|w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

Q. Let P be a regular language and Q be context-free language such that Q ⊆ P. (For example, let P be the language represented by the regular expression p*q* and Q be {p^nq^n|n ∈ N}). Then which of the following is ALWAYS regular?

Q. Consider the language L1,L2,L3 as given below.

L1={0^p1^q | p,q ∈ N}
L2={0^p1^q| p,q ∈ N and p=q}
L3={0^p1^q0^r | p,q,r ∈N and p=q=r}
Which of the following statements is NOT TRUE?

Q. Definition of a language L with alphabet {a} is given as following. L= { a^(nk) | k > 0, and n is a positive integer constant}. What is the minimum number of states needed in a DFA to recognize L?

Q. Which of the following pairs have DIFFERENT expressive power?

Q. 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’ (complement of 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?

Q. Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?

Q. Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true ?

Q. Consider the following two statements:

S1: { 0^2n |n >= l} is a regular language
S2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regular language

Which of the following statements is correct?

Q. Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least