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

View solution

Q. Define languages L0 and L1 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 = L0 ∪ L1. Which of the following is true ?

View solution

Q. The language {a^m b^n C^(m+n) | m, n ≥ 1} is

View solution

Q. Consider the following grammar G:

S → bS | aA | b
A → bA | aB
B → bB | aS | a

Let Na(w) and Nb(w) denote the number of a's and b's in a string w respectively. The language L(G) ⊆ {a, b}+ generated by G is

View solution

Q. L1 is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as w1, w2, w3, ... Define another language L2 over Σ Union {#} as {wi # wj : wi, wj ∈ L1, 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 ?

View solution

Q. Consider the languages L1 = {0^i1^j | i != j}. L2 = {0^i1^j | i = j}. L3 = {0^i1^j | i = 2j+1}. L4 = {0^i1^j | i != 2j}.

View solution

Q. S -> aSa|bSb|a|b; The language generated by the above grammar over the alphabet {a,b} is the set of

View solution

Q. The language L= {0^i21^i | i≥0 } over the alphabet {0,1, 2} is:

View solution

Q. Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rules

S --> aB S --> bA
B --> b A --> a
B --> bS A --> aS
B --> aBB A --> bAA

Which of the following strings is generated by the grammar?

View solution

Q. 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?

View solution

Q. Consider the languages:

L1 = {a^nb^nc^m | n, m > 0}
L2 = {a^nb^mc^m | n, m > 0}

Which one of the following statements is FALSE?

View solution

Q. Consider the languages:

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

Which one of the following is TRUE?

View solution

Q. Which of the following languages are context-free?

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

View solution

Q. Which one of the following statements is FALSE ?

View solution

Q. Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet {Z0, X} where Z0 is the bottom-of-stack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition (s, b, X) → (t, XZ0) means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols Z0 and X (in that order) on the stack.

(s, a, Z0) → (s, XXZ0)
(s, ϵ, Z0) → (f, ϵ)
(s, a, X) → (s, XXX)
(s, b, X) → (t, ϵ)
(t, b, X) → (t,.ϵ)
(t, c, X) → (u, ϵ)
(u, c, X) → (u, ϵ)
(u, ϵ, Z0) → (f, ϵ)

The language accepted by the PDA is

View solution

Q. A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.

S→aS∣A
A→aAb∣bAa∣ϵ

Which of the following strings is generated by the grammar above?

View solution

Q. Consider 2 scenarios:

C1: For DFA (ϕ, Ʃ, δ, qo, F),
if F = ϕ, then L = Ʃ*

C2: For NFA (ϕ, Ʃ, δ, qo, F),
if F = ϕ, then L = Ʃ*

Where F = Final states set
ϕ = Total states set

Choose the correct option ?

View solution

Q. Let G be the CFG, l be the number of left most derivations, r be the number of right most derivations and P be the number of parse trees. Assume l , r and P are computed for a particular string. For a given CFG ‘G’ and given string ‘w’, what is the relation between l , P , r ?

View solution

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

View solution

Q. 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?

(A) L2 – L1 is recursively enumerable.
(B) L1 – L3 is recursively enumerable
(C) L2 ∩ L1 is recursively enumerable
(D) L2 ∪ L1 is recursively enumerable.

View solution