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?

    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 one of the following languages over Σ = {a,b} is NOT context-free?

1. L is deterministic context-free.
2. L is context-free but not deterministic context-free.
3. L is not LL(k) for any k.

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 order of a language L is defined as the smallest k such that L^k = L^k+1.

Consider the language L₁ (over alphabet 0) accepted by the following automaton.

The order of L₁ is ______.

Consider the following languages:

I. {a^mbⁿc^pd^q ∣ m + p = n + q, where m, n, p, q ≥ 0}
II. {a^mbⁿc^pd^q ∣ m = n and p = q, where m, n, p, q ≥ 0}
III. {a^mbⁿc^pd^q ∣ m = n = p and p ≠ q, where m, n, p, q ≥ 0}
IV. {a^mbⁿc^pd^q ∣ mn = p + q, where m, n, p, q ≥ 0}

Which of the above languages are context-free?

Consider the following problems. L(G) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M.

(I) For an unrestricted grammar G and a string w, whether w∈L(G)
(II) Given a Turing machine M, whether L(M) is regular
(III) Given two grammar G₁ and G₂, whether L(G₁) = L(G₂)
(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 statement is correct?

Consider the following context-free grammar over the alphabet Σ = {a, b, c} with S as the start symbol:

S → abScT | abcT
T → bT | b

Which one of the following represents the language generated by the above grammar?

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 _________.

If G is a grammar with productions

where S is the start variable, then which one of the following strings is not generated by G?

Consider the context-free grammars over the alphabet {a, b, c} given below. S and T are non-terminals.

G₁: S → aSb|T, T → cT|ϵ
G₂: S → bSa|T, T → cT|ϵ

The language L(G₁) ∩ L(G₂) is

Consider the following languages over the alphabet Σ = {a, b, c}.
Let L₁ = {aⁿ bⁿ c^m│m,n ≥ 0} and L₂ = {a^m bⁿ cⁿ│m,n ≥ 0}

Which of the following are context-free languages?

I. L₁ ∪ L₂
II. L₁ ∩ L₂

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 _________.

Consider the following languages:

L₁ = {a^p│p is a prime number}
L₂ = {aⁿ b^m c^2m | n ≥ 0, m ≥ 0}
L₃ = {aⁿ bⁿ c²ⁿ │ n ≥ 0}
L₄ = {aⁿ bⁿ │ n ≥ 1}

Which of the following are CORRECT?

I. L₁ is context-free but not regular.
II. L₂ is not context-free.
III. L₃  is not context-free but recursive.
IV. L₄ is deterministic context-free.

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)?

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

Which of the following decision problems are undecidable?

I. Given NFAs N₁ and N₂, is L(N₁)∩L(N₂) = Φ?
II. Given a CFG G = (N,Σ,P,S) and a string x ∈ Σ*, does x ∈ L(G)?
III. Given CFGs G₁ and G₂, is L(G₁) = L(G₂)?
IV. Given a TM M, is L(M) = Φ?

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?

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

Language L₁ is defined by the grammar: S₁ → aS₁b|ε
Language L₂ is defined by the grammar: S₂ → abS₂|ε

Consider the following statements:

P: L₁ is regular
Q: L₂ is regular

Which one of the following is TRUE?

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

Consider the following two statements:

I. If all states of an NFA are accepting states then the language accepted by the NFA is Σ*.
II. There exists a regular language A such that for all languages B, A∩B is regular.

Which one of the following isCORRECT?

Consider the following languages:

L₁ = {aⁿ b^m c^n+m : m,n ≥ 1}
L₂ = {aⁿ bⁿ c²ⁿ : n ≥ 1}

Which one of the following isTRUE?

Consider the following languages.

L₁ = {〈M〉|M takes at least 2016 steps on some input},
L₂ = {〈M〉│M takes at least 2016 steps on all inputs} and
L₃ = {〈M〉|M accepts ε},

where for each Turing machine M, 〈M〉 denotes a specific encoding of M. Which one of the following is TRUE?

A student wrote two context-free grammars G1 and G2 for generating a single C-like array declaration. The dimension of the array is at least one. For example,

int a[10][3];

Grammar G1               Grammar G2
D → intL;                 D → intL;
L → id[E                  L → idE
E → num]                  E → E[num]
E → num][E                E → [num]

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?

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

L1 = {ambnanbm ⎪ m, n ≥ 1}
L2 = {ambnambn ⎪ m, n ≥ 1}
L3 = {ambn ⎪ m = 2n + 1}

Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers i, j with i < j.  Given a shortcut i, j if you are at position i on the number line, you may directly move to j. Suppose T(k) denotes the smallest number of steps needed to move from k to 100. Suppose further that there is at most 1 shortcut involving any number, and in particular from 9 there is a shortcut to 15. Let y and z be such that T(9) = 1 + min(T(y),T(z)).  Then the value of the product yz is _____.

1. For every non-deterministic Turing machine, 
   there exists an equivalent deterministic Turing machine.
2. Turing recognizable languages are closed under union 
   and complementation.
3. Turing decidable languages are closed under intersection 
   and complementation.
4. Turing recognizable languages are closed under union 
   and intersection.

1. The problem of determining whether there exists
   a cycle in an undirected graph is in P.
2. The problem of determining whether there exists
   a cycle in an undirected graph is in NP.
3. If a problem A is NP-Complete, there exists a 
   non-deterministic polynomial time algorithm to solve A.

1. Complement of L(A) is context-free.
2. L(A) = L((11*0+0)(0 + 1)*0*1*)
3. For the language accepted by A, A is the minimal DFA.
4. A accepts all strings over {0, 1} of length at least 2.

Which of the following problems are decidable?

2. e+ 0 (10 * 1 + 00) * 0
3. e+ 0 (10 * 1 + 10) * 1
4. e+ 0 (10 * 1 + 10) * 10 *

G = {S → SS, S → ab, S → ba, S → Ε}
I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III. G can be accepted by a deterministic PDA.

L1 = {wwR |w ∈ {0, 1}*}
L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbol
L3 = {ww |  w ∈  (0, 1}*)

Let N_f and N_p denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let D_f and D_p denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata, respectively. Which one of the following is TRUE?