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?

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

Let L₁ = {w ∈ {0,1}* |w has at least as many occurrences of (110)’s as (011)’s}. Let L₂ = {w ∈ {0,1}*|w has at least as many occurrences of (000)’s as (111)’s}. Which one of the following is TRUE?

The length of the shortest string NOT in the language (over Σ = {a b,} of the following regular is expression is ______________.

     a*b*(ba)*a* 

Let Σ be a finite non-empty alphabet and let 2^Σ* be the power set of Σ*. Which one of the following is TRUE?

Which one of the following problems is undecidable?

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

Consider the following languages over the alphabet Σ = {0,1,c}:

L₁ = {0ⁿ1ⁿ | n≥0}
L₂ = {w^cw^r | w∈{0,1}*}
L₃ = {ww^r | w∈{0,1}*}

Here, w^r is the reverse of the string . Which of these languages are deterministic Context-free languages?

Consider the decision problem 2CNFSAT defined as follows:

{Φ|Φ is a satisfiable propositional formula in CNF with atmost two literals per clause}
For example, is a Boolean formula and it is in 2CNFSAT.

The decision problem 2CNFSAT is

Which of the following statements is/are FALSE?

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.

Which of the following statements are TRUE?

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.

Consider the DFA given.

Which of the following are FALSE?

Which of the following are FALSE?

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 is/are undecidable?

1. G is a CFG. Is L(G) = Φ?
2. G is a CFG. Is L(G) = Σ*?
3. M is a Turing machine. Is L(M) regular?
4. A is a DFA and N is an NFA. Is L(A) = L(N)?

What is the complement of the language accepted by the NFA shown below?

Assume Σ={a} and ε is the empty string.

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 also context-free?

3) If L is a regular language, then, is also regular?

4) If L is a recursive language, then, is also recursive?

Given the language L ={ab,aa,baa}, which of the following strings are in L *?

1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa

Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below.

The missing arcs in the DFA are

Let P be a regular language and Q be a 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ⁿqⁿ | n ∈ N]). Then which of the following is ALWAYS regular?

Which of the following pairs have DIFFERENT expressive power?

Definition of a language L with alphabet {a} is given as following.

L = {ank| k>0, and n is a positive integer constant}

What is the minimum number of states needed in a DFA to recognize L?

Consider the languages L1,L2 and L3 as given below.

L1 = {0^p1^q|p,q∈N},
L2 = {0^p1^q|p,q∈N and p=q} and
L3 = {0^p1^q0^r|p,q,r∈N and p=q=r}.

Which of the following statements is NOT TRUE?

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

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?

Consider the languages

L1 = {0ⁱ1^j | i != j}.
L2 = {0ⁱ1^j | i = j}.
L3 = {0ⁱ1^j | i = 2j+1}.
L4 = {0ⁱ1^j | i != 2j}.

Which one of the following statements is true?

Let w be any string of length n is {0, 1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?

The language generated by the above grammar over the alphabet {a,b} is the set of

Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?

Which one of the following is FALSE?

Given the following state table of an FSM with two states A and B, one input and one output:

If the initial state is A = 0, B = 0, what is the minimum length of an input string which will take the machine to the state A = 0, B = 1 with Output = 1?

Let L = L1 ∩ L2, where L1 and L2 are languages as defined below:

L1 = {a^mb^mcaⁿbⁿ | m,n ≥ 0 }
L2 = {aⁱb^jc^k | i,j,k ≥ 0 }

Then L is

The above DFA accepts the set of all strings over {0,1} that

Which of the following is true for the language {a^p|p is a prime} ?

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

If L and are recursively enumerable, then L is

Which of the following statements is false?

Given below are two finite state automata (→ indicates the start state and F indicates a final state)

Which of the following represents the product automaton Z×Y?

Which of the following statements are true?

I. Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa
II. All \epsilon productions can be removed from any context-free grammar by suitable transformations
III. The language generated by a context-free grammar all of whose productions are of the form X → w or X → wY (where, w is a string of terminals and Y is a non-terminal), is always regular
IV. The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees

Match the following:

Match the following NFAs with the regular expressions they correspond to

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

Which of the following are regular sets?

I. {aⁿb^2m | n≥0, m≥0}
II. {aⁿb^m | n=2m}
III. {aⁿb^m | n≠2m}
IV. {xcy | x,y∈{a,b}*}

Which of the following problems is undecidable?

Which of the following is TRUE?

A minimum state deterministic finite automaton accepting the language L = {w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} has

The language L = {0ⁱ21ⁱ | i≥0} over the alphabet {0, 1, 2} is: 

Which of the following languages is regular? 

Consider the following Finite State Automaton.

The language accepted by this automaton is given by the regular expression

Consider the following Finite State Automaton.

The minimum state automaton equivalent to the above FSA has the following number of states

Let L₁ = {0^n+m1ⁿ0^m|n,m ≥ 0}, L₂ = {0^n+m1^n+m0^m|n,m ≥ 0}, and L₃ = {0^n+m1^n+m0^n+m|n,m ≥ 0}. Which of these languages are NOT context free?

If s is a string over (0 + 1)* then let n₀(s) denote the number of 0’s in s and n₁(s) the number of 1’s in s. Which one of the following languages is not regular?

For S ∈ (0+1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s ∈ (0+1)*|d(s)mod5 = 2 and d(s)mod7 = 4}.

Which one of the following statements is true?

Consider the following statements about the context free grammar

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.

Which combination below expresses all the true statements about G?

Let L₁ be a regular language, L₂ be a deterministic context-free language and L₃ a recursively enumerable, but not recursive, language. Which one of the following statements is false?

Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting this languages is:

Which one of the following grammars generates the language L = {aⁱb^j|i≠j}?

In the correct grammar of above question, what is the length of the derivation (number of steps starting from S) to generate the string a^lb^m with l≠m?

Consider three decision problems P₁, P₂ and P₃. It is known that P₁ is decidable and P₂ is undecidable. Which one of the following is TRUE?

Consider the machine M:

The language recognized by M is:

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?

Consider the languages:

L1 = {anbncm |n,m > 0} and L2 = {anbmcm |n,m > 0}

Which one of the following statements is FALSE?

Let L₁ be a recursive language, and let L₂ be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

Consider the languages:

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

Which one of the following is TRUE?

The following diagram represents a finite state machine which takes as input a binary number from the least significant bit.

Which one of the following is TRUE?

The following finite state machine accepts all those binary strings in which the number of 1's and 0's are respectively.

The language {a^m bⁿ C^m+n | m, n ≥ 1} is

L₁ is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as w₁, w₂, w₃, ... Define another language L₂ over Σ Union {#} as {w_i # w_j : w_i, w_j ∈ L₁, i < j}. Here # is a new symbol. Consider the following assertions.

S1: L1 is recursive implies L2 is recursive
S2: L2 is recursive implies L1 is recursive

Which of the following statements is true?

Nobody knows yet if P = NP. Consider the language L defined as follows:

Which of the following statements is true?

The regular expression 0*(10*)* denotes the same set as

If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?

Consider the following deterministic finite state automaton M.

Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is

Let G = ({S},{a,b},R,S) be a context free grammar where the rule set R is S → aSb | SS | ε Which of the following statements is true?

Consider two languages L₁ and L₂ each on the alphabet ∑. Let f: ∑ → ∑ be a polynomial time computable bijection such that (∀ x)[x ∈ L₁ iff f(x) ∈ L₂]. Further, let f^-1 be also polynomial time computable.

Which of the following CANNOT be true?

A single tape Turing Machine M has two states q₀ and q₁, of which q₀ is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table.

The table is interpreted as illustrated below. The entry (q₁, 1, R) in row q₀ and column 1 signifies that if M is in state q₀ and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q₁.

Which of the following statements is true about M?

Define languages L₀ and L₁ as follows:

L0 = {〈M, w, 0〉 | M halts on w}
L1 = {〈M, w, 1〉 | M does not halts on w} 

Here 〈M, w, i〉 is a triplet, whose first component. M, is an encoding of a Turing Machine, second component, w, is a string, and third component, i, is a bit.

Let L = L₀∪L₁. Which of the following is true?

Consider the NFA M shown below.

Let the language accepted by M be L. Let L₁ be the language accepted by the NFA M₁, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?

The language accepted by a Pushdown Automaton in which the stack is limited to 10 items is best described as

The Finite state machine described by the following state diagram with A as starting state, where an arc label is x/y and x stands for 1-bit input and y stands for 2- bit output

The smallest finite automaton which accepts the language {x|length of x is divisible by 3} has

Which of the following is true?

The C language is:

The aim of the following question is to prove that the language {M| M is the code of a Turing Machine which, irrespective of the input, halts and outputs a 1}, is undecidable. This is to be done by reducing form the language {M',x| M' halts on x}, which is known to be undecidable. In parts (a) and (b) describe the 2 main steps in the construction of M. in part (c) describe the key property which relates the behaviour of M on its input w to the behaviour of M′ on x.

(a) On input w, what is the first step that M must make?
(b) On input w, based on the outcome of the first step, what is the second step that M must make?
(c) What key property relates the behaviour of M on w to the behaviour of M′ on x?

We require a four state automaton to recognize the regular expression (a|b)*abb.

(a) Give an NFA for this purpose.
(b) Give a DFA for this purpose.

Consider the following two statements:

S1: {0²ⁿ|n≥1|} is a regular language
S2: {0^m1ⁿ0^m+n|m≥1 and n≥1|} is a regular language

Which of the following statements is correct?

Which of the following statements is true?

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

Consider a DFA over Σ = {a,b} accepting all strings which have number of a's divisible by 6 and number of b's divisible by 8. What is the minimum number of states that the DFA will have?

Consider the following languages:

L1 = {ww|w ∈ {a,b}*}
L2 = {ww^R|w ∈ {a,b}*, w^R is the reverse of w}
L3 = {0²ⁱ|i is an integer}
L3 = {0ⁱ²|i is an integer}

Which of the languages are regular?

Consider the following problem X.

Given a Turing machine M over the input alphabet Σ, any state q of M And a word w∈Σ*, does the computation of M on w visit the state q?

Which of the following statements about X is correct?

Construct DFA’s for the following languages:

 (a) L = {w|w ∈ {a,b}*, w has baab as a subsring } 
 (b) L = {w|w ∈ {a,b}*, w has an odd number of a's and an odd number of b's} 

Give a deterministic PDA for the language L = {aⁿcb²ⁿ|n ≥ 1} over the alphabet Σ = {a,b,c}. Specify the acceptance state.

Let a decision problem X be defined as follows:

    X: Given a Turing machine M over Σ and nay word w ∈ Σ,
       does M loop forever on w? 

You may assume that the halting problem of Turing machine is undecidable but partially decidable.

(a) Show that X is undecidable.
(b) Show that X is not even partially decidable.

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?

Let L denotes the language generated by the grammar S → 0S0/00.
Which of the following is true?

What can be said about a regular language L over {a} whose minimal finite state automation has two states?

Consider the following decision problems:

(P1) Does a given finite state machine accept a given string
(P2) Does a given context free grammar generate an infinite number of stings

Which of the following statements is true?