Theory of Compu...

Consider the languages L₁ = Φ and L₂ ={a}. Which one of the following represents \({L_1}L_2^* \cup L_1^*\)?

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?

For x ϵ (0 + 1)^* Let L = { x ϵ (0 + 1)^* | dec(s) mod 7 = 1 and dec(s) mod 11 = 3 } where dec(7) = 111 since d(s) denotes the decimal value.

Which one of the following statements is true?

Consider the following grammar:

S → 0A|0BB

A → 00A|λ

B → 1B|11C

C → B

Which language does this grammar generate?

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

If any string of a language L can be effectively enumerated by an enumerator in a lexicographic order, then language L is _______

If a Context Free Grammar G is in Chomsky Normal Form, to derive a string of length 101 number of productions needed is _____.

Consider the following context-free grammar:

S → AB

A → aAb/ab

B → cBd/cd

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

The number of two states DFA can be constructed with a designated initial state and a designated final state over the alphabet ∑ = {x, y} is _____.

The string 1101 does not belong to the set represented by:

Consider the following languages:

\({L_1} = \left\{ {{a^n}{b^n}{c^m}} \right\} \cup \left\{ {{a^n}{b^m}{c^m}} \right\},\;n,\;m \ge 0\)

\({L_2} = \{ w{w^R}|w \in \left\{ {a,\;b} \right\}*\}\) Where R represents reversible operation.

Which productions should be added in the following context-free grammar to get a set of all palindromes over the input {0,1}?

P → ε

P  → 0P0

P → 1P1

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

Let the minimum state DFA accepting the language L₁ = {x| x ϵ {p, q}* } in which number of p’s and q’s in x are divisible by 10 and 15 be n and the minimum number of state DFA accepting the language L₂ = { w | w ϵ {a}* } in which a is divisible by 10 and 15 be y. The value of x – y is _____.

Which one of the following is FALSE?

Which of the following language is decidable?

Which of the following are not context free?

L₁: { aⁿ b^m a^k | k = mn and k, m, n ≥ 1 }

L₂: { a^{m + n} b^{n + m} c^m | n, m ≥ 1 }

L₃: { aⁿ bⁿ c^m | m < n and m, n ≥ 1 }

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?

Let A be a recursively enumerable language which is not recursive and A’ be its complement, also B be recursive language and B’ be its complement. Let X and Y be two languages such that A’ reduces to X and Y reduces to B’ and the reduction is many to one. Which of the following is/are true?

Recursive languages are closed under which of the following operations?

I. Union

II. Complement

III. Concatenation

IV. Kleene star

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

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 *

Consider the language L = {an |n ≥ 0} ∪ {anbn| n ≥ 0} and the following statements.

Which of the above statements is/are TRUE?

Which of the following is decidable for language L?

I. For a context sensitive language, L = ϕ

II. For a context free language, L = ∑^*

III. For a deterministic context free language, L is finite

Which of the following is/are not equivalent regular expressions?