If L is a regular language over Σ = {a,b}, which one of the following languages is NOT regular?

For Σ = {a,b}, let us consider the regular language L = {x|x = a^2+3k or x = b^10+12k, k ≥ 0}. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?

Consider the following sets:

S1.  Set of all recursively enumerable languages over the alphabet {0,1}
S2.  Set of all syntactically valid C programs
S3.  Set of all languages over the alphabet {0,1}
S4.  Set of all non-regular languages over the alphabet {0,1}

Which of the above sets are uncountable?

Which one of the following languages over Σ = {a,b} is NOT context-free?

Let Σ be the set of all bijections from {1, …, 5} to {1, …, 5}, where id denotes the identity function i.e. id(j) = j,∀j. Let º denote composition on functions. For a string x = x₁ x₂ … x_n ∈ Σⁿ, n ≥ 0. Let π(x) = x₁ º x₂ º … º x_n.

Consider the language L = {x ∈ Σ* | π(x) = id}. The minimum number of  states in any DFA accepting L is ______.

Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?

The set of all recursively enumerable languages is

Consider the language L given by the regular expression (a+b)*b(a+b) over the alphabet {a,b}. The smallest number of states needed in deterministic finite-state automation (DFA) accepting L is _________.

Let A and B be finite alphabets and let # be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is computable if there exists a Turing machine M which given an input x in A*, always halts with f(x) on its tape. Let L_f denote the language {x # f(x)│x ∈ A*}. Which of the following statements is true:

Let L₁, L₂ be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT?

Identify the language generated by the following grammar, where S is the start variable.

                                     S → XY
                                     X → aX|a
                                     Y → aYb|ϵ

The minimum possible number of a deterministic finite automation that accepts the regular language L = {w₁aw₂ | w₁, w₂ ∈ {a,b}*, |w₁| = 2,|w₂| ≥ 3} is _________.

Let δ denote the transition function and denote the extended transition function of the ε-NFA whose transition table is given below:

Then  is

Which of the following languages is generated by the given grammar?

Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?

Consider the following context-free grammars:

G1: S → aS|B, B → b|bB
G2: S → aA|bB, A → aA|B|ε, B → bB|ε

Which one of the following pairs of languages is generated by G₁ and G₂, respectively?

Consider the transition diagram of a PDA given below with input alphabet Σ = {a,b} and stack alphabet Γ = {X,Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA.

Which one of the following is TRUE?

Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that  reduces to W, and Z reduces to  (reduction means the standard many-one reduction). Which one of the following statements is TRUE?

The number of states in the minimum sized DFA that accepts the language defined by the regular expression

Consider the following types of languages: L₁: Regular, L₂: Context-free, L₃ : Recursive, L₄ : Recursively enumerable. Which of the following is/are TRUE?

For any two languages L₁ and L₂ such that L₁ is context-free and L₂ is recursively enumerable but not recursive, which of the following is/are necessarily true?

Consider the DFAs M and N given above. The number of states in a minimal DFA that accepts the language L(M) ∩ L(N) is __________.

Consider the NPDA 〈Q = {q0, q1, q2}, Σ = {0, 1}, Γ = {0, 1, ⊥}, δ, q0, ⊥, F = {q2}〉, where (as per usual convention) Q is the set of states, Σ is the input alphabet, Γ is stack alphabet, δ is the state transition function, q0 is the initial state, ⊥ is the initial stack symbol, and F is the set of accepting states, The state transition is as follows:

Consider two decision problems Q₁, Q₂ such that Q₁ reduces in polynomial time to 3-SAT and 3 -SAT reduces in polynomial time to Q₂. Then which one of following is consistent with the above statement?

Consider the following statements:

I. The complement of every Turning decidable language is Turning decidable
II. There exists some language which is in NP but is not Turing decidable
III. If L is a language in NP, L is Turing decidable

Which of the above statements is/are True?

Which of the following language is/are regular ?

L1: {wxw^R ⎪ w, x ∈ {a, b}* and ⎪w⎪, ⎪x⎪ >0} w^R is the reverse of string w
L2: {aⁿb^m ⎪m ≠ n and m, n≥0}
L3: {a^pb^qc^r ⎪ p, q, r ≥ 0}

The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0 + 1) * (10) is __________.

Consider alphabet ∑ = {0, 1}, the null/empty string λ and the sets of strings X₀, X₁ and X₂ generated by the corresponding non-terminals of a regular grammar. X₀, X₁ and X₂ are related as follows:

X₀ = 1 X₁
X₁ = 0 X₁ + 1 X₂
X₂ = 0 X₁ + {λ}

Which one of the following choices precisely represents the strings in X₀?

Let L be the language represented by the regular expression Σ*0011Σ* where Σ = {0,1}. What is the minimum number of states in a DFA that recognizes (complement of L)?

Language L1 is polynomial time reducible to language L2. Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are True?

I. If L4 ∈ P, L2 ∈ P
II. If L1 ∈ P or L3 ∈ P, then L2 ∈ P
III. L1 ∈ P, if and only if L3 ∈ P
IV. If L4 ∈ P, then L1 ∈ P and L3 ∈ P

Which of the following languages are context-free?

L1 = {a^mbⁿaⁿb^m ⎪ m, n ≥ 1}
L2 = {a^mbⁿa^mbⁿ ⎪ m, n ≥ 1}
L3 = {a^mbⁿ ⎪ m = 2n + 1}

Which one of the following is TRUE?

Consider the finite automaton in the following figure.

What is the set of reachable states for the input string 0011?

If L₁ = {aⁿ|n≥0} and L₂ = {bⁿ|n≥0}, consider

(I) L₁·L₂ is a regular language
(II) L₁·L₂ = {aⁿbⁿ|n≥0}

Which one of the following is CORRECT?

Let A≤_mB denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?