Theory of Computation Demo Test Series-3
Q: Consider the grammar
S ---> PQ | SQ | PS
P ---> x
Q--> y
To get a string of n terminals, the number of productions to be used is ...
- A: 2n - 1
- B: n^{2}
- C: n+1
- D: None
Q: Let L = L1âŠL2, where L1 and L2 are languages as defined below:
L1 = {a^{m}b^{m}ca^{n}b^{n} | m, n >= 0 }
L2 = {a^{i}b^{j}c^{k} | i, j, k >= 0 }
Then L is ...
- A: Not recursive
- B: Context free but not regular
- C: Regular
- D: Recursively enumerable but not context free.
Q: The language L = (0n 1n 2n where n > 0) is a ...
- A: context free language
- B: context-sensitive language
- C: regular language
- D: recursive enumerable language
Q: Which of the following pairs have DIFFERENT expressive power?
- A: Deterministic push down automata(DPDA)and Non-deterministic push down automata(NPDA)
- B: Deterministic finite automata(DFA) and Non-deterministic finite automata(NFA)
- C: Deterministic single-tape Turing machine and Non-deterministic single-tape Turing machine
- D: Single-tape Turing machine and multi-tape Turing machine
Q: If every string of a language can be determined, whether it is legal or illegal in finite time, the language is called
- A: undecidable
- B: interpretive
- C: decidable
- D: non-deterministic
Q: The defining language for developing a formalism in which language definitions can be stated, is called
- A: intermediate language
- B: decidable language
- C: syntactic meta language
- D: high level language
Q: Consider a grammar :
G = { { S } , { 0 , 1 } , p , s }
where elements of p are:
S --> ss
S--> 0S1
S--> 1S0
S--> empty
The grammer will generate ...
- A: context-sensitive language
- B: regular language
- C: recursive enumerable language
- D: context-free language
Q: Consider the following grammar
S --> Ax / By
A --> By/Cw
B --> x / Bw
C--> y
Which of the regular expressions describe the same set of strings as the grammar ?
- A: xw * y + xw * yx + ywx
- B: xwy + xw * xy + ywx
- C: xw * y + xw x yx + ywx
- D: xw xy + xww * y + ywx
Q: The logic of pumping lemma is a good example of ...
- A: pigeon-hole principle
- B: divide-and-conquer technique
- C: recursion
- D: iteration
Q: If L1 and L2 are context free language and R a regular set, then which one of the languages below is not necessarily a context free language?
- A: L1 ∩ L2
- B: L1 ∩ R
- C: L1 L2
- D: L1 ∪ L2