Theory Of Computation And Compiler Design Set 2 MCQs

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

The set of all strings containing the substring 00.
The set of all strings containing at most two 0’s.
The set of all strings containing at least two 0’s.
The set of all strings that begin and end with either 0 or 1.

Answer: The set of all strings containing at least two 0’s.

Q2 | Which one of the following is FALSE?

There is unique minimal DFA for every regular language
Every NFA can be converted to an equivalent PDA.
Complement of every context-free language is recursive.
Every nondeterministic PDA can be converted to an equivalent deterministic PDA.

Answer: Every nondeterministic PDA can be converted to an equivalent deterministic PDA.

Q3 | Match all items in Group 1 with correct options from those given in Group 2.List I List IIP. Regular Expression 1. Syntax analysisQ. Push down automata 2. Code GenerationR. Dataflow analysis 3. Lexical analysisS. Register allocation 4. Code optimization

P-4. Q-1, R-2, S-3
P-3, Q-1, R-4, S-2
P-3, Q-4, R-1, S-2
P-2, Q-1, R-4, S-3

Answer: P-3, Q-1, R-4, S-2

Q4 | Which of the following pairs have DIFFERENT expressive power?

Deterministic finite automata (DFA) and Non-Deterministic finite automata(NFA)
Deterministic push down automata (DPDA) and Non-deterministic pushdown automata
Deterministic single-tape Turing machine and Non-deterministic single-tape Turing Machine
Single-tape Turing machine and multi-tape Turing machine

Answer: Deterministic push down automata (DPDA) and Non-deterministic pushdown automata

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

ScT (S is a subset of T)
TcS (T is a subset of S)
S=T
SnT=Ø

Answer: S=T

Q6 | Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?

L = O
L is regular but not O
L is context free but not regular
L is not context free

Answer: L is regular but not O

Q7 | Consider the following two statements:S1: { 0^2n |n >= l} is a regu1ar languageS2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar languageWhich of the following statements is correct?

Only S1 is correct
Only S2 is correct
Both S1 and S2 are correct
None of S1 and S2 is correct

Answer: Both S1 and S2 are correct

Q8 | Which of the following statements in true?

If a language is context free it can always be accepted by a deterministic push-down automaton
The union of two context free languages is context free
The intersection of two context free languages is context free
The complement of a context free language is context free

Answer: The union of two context free languages is context free

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

N^2
2^N
2N
N!

Answer: 2^N

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

It is not accepted by a turing machine
It is regular but not context free
It is context free but not regular
It is neither regular nor context free but accepted by a turing machine

Answer: It is neither regular nor context free but accepted by a turing machine

Q11 | Which of the following are decidable ?1. whether the intersection of two regular language is infinite.2. whether a give context free language is regular3. whether two push down automata accept the same language.4. whether a given grammar is context free

1 and 2
1 and 4
2 and 3
2 and 4

Answer: 1 and 4

Q12 | If L and L' are recursively enumerable, then L is

regular
context free
context sensitive
recursive

Answer: recursive

Q13 | 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 rulesS --> aB S --> bAB --> b A --> aB --> bS A --> aSB --> aBB A --> bAAWhich of the following strings is generated by the grammar?

aaaabb
aabbbb
aabbab
abbbba

Answer: aabbab

Q14 | Consider the following context free languages:L1 = {0^i 1^j 2^k | i+j = k}L2 = {0^i 1^j 2^k | i = j or j = k}L3 = {0^i 1^j | i = 2j+1}Which of the following option is true?

L1, L2 and L3 can be recognized by Deterministic Push down automata
L1, L2 can be recognized by Deterministic Push down automata
L1, L3 can be recognized by Deterministic Push down automata
None of the above

Answer: L1, L3 can be recognized by Deterministic Push down automata

Q15 | Which of the following are decidable?I. Whether the intersection of two regular languages is infiniteII. Whether a given context-free language is regularIII. Whether two push-down automata accept the same languageIV. Whether a given grammar is context-free

I and II
I and IV
II and III
II and IV

Answer: I and IV

Q16 | Let be the encoding of a Turing machine as a string over ?= {0, 1}. Let L = { |M is a Turing machine that accepts a string of length 2014 }. Then, L is

decidable and recursively enumerable
undecidable but recursively enumerable
undecidable and not recursively enumerable
decidable but not recursively enumerable

Answer: undecidable but recursively enumerable

Q17 | Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?

P3 is decidable if P1 is reducible to P3
P3 is undecidable if P3 is reducible to P2
P3 is undecidable if P2 is reducible to P3
P3 is decidable if P3 is reducible to P2's complement

Answer: P3 is undecidable if P2 is reducible to P3

Q18 | 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 stingsWhich of the following statements is true?

Both (P1) and (P2) are decidable
Neither (P1) nor (P2) are decidable
Only (P1) is decidable
Only (P2) is decidable

Answer: Both (P1) and (P2) are decidable

Q19 | Which of the following statements is false?

Every context-sensitive language is recursive.
The set of all languages that are not recursively enumerable is countable.
The family of recursively enumerable languages is closed under union.
The families of recursively enumerable and recursive languages are closed under reversal

Answer: The set of all languages that are not recursively enumerable is countable.

Q20 | In some programming languages, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denotes the set of letters and digit respectively. Which of the following expression defines an identifier?

(L + D) *
(L.D) *
L(L + D) *
L(L.D) *

Answer: L(L + D) *

Q21 | The number of strings of length 4 that are generated by the regular expression (0+1+|2+3+)*, where | is an alternation character and {+, *} are quantification characters, is:

8
9
10
12

Answer: 10

Q22 | The regular grammar for the language L = {anbm | n + m is even} is given by

S ? S1 | S2 S1 ? a S1| A1 A1 ? b A1| ? S2 ? aaS2| A2 A2 ? b A2| ?
S ? S1 | S2 S1 ? a S1| aA1 S2 ? aaS2| A2 A1 ? b A1| ? A2 ? b A2| ?
S ? S1 | S2 S1 ? aaa S1| aA1 S2 ? aaS2| A2 A1 ? b A1| ? A2 ? b A2| ?
S ? S1 | S2 S1 ? aa S1| A1 S2 ? aaS2| A2 A1 ? bb A1| ? A2 ? bb A2| ?

Q23 | Consider the following identities for regular expressions: (a) (r + s)* = (s + r)* (b) (r*)* = r* (c) (r* s*)* = (r + s)* Which of the above identities are true?

(a) and (b) only
(b) and (c) only
(c) and (a) only
(a), (b) and (c)

Answer: (a), (b) and (c)

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

L is recursively enumerable, but not recursive
L is recursive, but not context-free
L is context-free, but not regular
L is regular

Answer: L is regular

Q25 | The number of tokens in the following C statement is (GATE 2000)printf("i = %d, &i = %x", i, &i);

3
26
10
21

Answer: 10