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?

View solution

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?

View solution

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?

View solution

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?

View solution

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?

View solution

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

View solution

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?

View solution

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?

View solution

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

View solution

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?

View solution

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

View solution