Q. Which of the following strings is in the language defined by grammar S→0A, A→1A/0A/1

View solution

Q. The logic of pumping lemma is a good example of:

View solution

Q. Let A = {x | -1< x< 1} = B. The function f(x)=x/2 from A to B is:

View solution

Q. Which sentence can be generated by S→d/bA, A→d/ccA:

View solution

Q. Regular expression a+b denotes the set:

View solution

Q. Which of the following is not true?

View solution

Q. Identify the language which is not context - free.

View solution

Q. The context-free languages are closed for:

(i) Intersection                          (ii) Union
(iii) Complementation             (iv) Kleene Star

View solution

Q. Grammars that can be translated to DFAs:

View solution

Q. The language accepted by a Push down Automata:

View solution

Q. In parallel algorithm design, the process of grouping tasks into larger tasks in order to improve performance:

View solution

Q. Recursive Descent Parsers are a type of:

View solution

Q. If language L={0,1}*, then the reversed language L^R =

View solution

Q. Let r = a(a + b)*, s = aa*b and t = a*b be three regular expressions.
Consider the following:

(i) L(s) ⊆ L(r) and L(s) ⊆ L(t)
(ii) L(r) ⊆ L(s) and L(s) ⊆ L(t)

Choose the correct answer from given below:

View solution

Q. Consider the language L given by

L = {2^(nk) ∣ k>0, and n is non-negative integer number}

The minimum number of states of finite automaton which accepts the language L is

View solution

Q. The number of substrings that can be formed from string given by

a d e f b g h n m p

is

View solution

Q. Consider the following two languages:

L1 = {x ∣ for some y with ∣y∣ = 2^∣x∣,xy ∈ L and L is regular language}
L2 = {x ∣ for some y such that ∣x∣ = ∣y∣, xy ∈ L and L is regular language}

Which one of the following is correct?

View solution

Q. Consider the following languages:

L1 = {a^(n+m) b^n a^m ∣ n,m ≥ 0}
L2 = {a^(n+m) b^(n+m) a^(n+m) ∣ n,m ≥ 0}

Which of the following is correct?

View solution

Q. Consider R to be any regular language and L1, L2 be any two context-free languages. Which of the following is correct?

View solution

Q. Consider the following problems:

(i) Whether a finite state automaton halts on all inputs?
(ii) Whether a given context free language is regular?
(iii) Whether a Turing machine computes the product of two numbers?

Which one of the following is correct?

View solution