Theory of Computation Solutions

THEORY OF COMPUTATION
Solutions
1. Number of trivial substrings in “GATE2013” are:
A. 37 B. 35 C. 2 D. 36
Solution: Option C
2. Let the string be defined over symbols a and b then what will be the number of states in minimal
DFA, if every string starts and ends with different symbols?
A. 5 B. 4 C. 3 D. None
Solution: Option A
3. The total number of substrings present in “GATE” is:
A. 7 B. 10 C. 11 D. 8
Solution: Option C
4. Let ∑= {a, b}, what are the number of states in minimal DFA, length of every string congruent
to mod 5.
A. 2 B. 3 C. 5 D. None
Solution: Option C
5. A minimal DFA that is equivalent to a NDFA has:
A. Always more states B. Always less no. of states

C. Exactly 2n states D. Sometimes more states
Solution: Option D
6. Consider following Regular Expression:

(i) a*b*b (a+ (ab)*)* b*
(ii) a*(ab + ba)* b*
What is length of shortest string which is in both (i) & (ii)?

A. 2 B. 3 C. 4 D. None
Solution: Option D
1
7. S AB
A BB/ a
B AB/ b
Choose incorrect statement?
A. aabbb can be derived from above grammar

B. aabb can be derived from above grammar
C. ababab can be derived from above grammar
D. abbb can be derived from above grammar
Solution: Option B
8. One of the following Regular Expressions is not the same as others. Which one?
A. (a* + b*a*)* B. (a*b* + b*a*)* (a*b*)*

C. ((ab)* + a*)* D. (a + b)* a*b*a*b*
Solution: Option C
9. The complement of CFL:
A. Recursive B. Recursive enumerated

C. Not RE D. The empty set
Solution: Option A
10. The language of primes in unary is:

A. Regular B. CFL C. DCFL D. Context Sensitive
Solution: Option D
11. Consider the regular grammar generating the set of all strings ending with ‘00’.
S 1S/ 0P
P 0C/ 0/ 1S
The production missing is

A. A  1S B. B C1 C. D C1 D. A∈
Solution: Option A
2
12. Consider a DFA with
1000000000000000000000000000 states, over the input alphabet consisting of all Greek

alphabet letters. What can we say about it?
A. It is not possible that it accepts the empty set.

B. It is not possible that it accepts only empty string.
C. It is not possible that it accepts strings of length 1 only.
D. It is possible that it accepts all strings over the input alphabet.
Solution: Option D
13. What are the number of states needed in minimal DFA, that accepts (1+1111)*
A. 5 B. 4 C. 1 D. None
Solution: Option C
14. Consider the grammar:

SaSbS/ bSaS/ ε,
The smallest string for which the grammar has two derivation trees:
A. abab B. aabb C. bbaa D. aaabbb
Solution: Option B
15. Consider the following languages:

L1= {anbn (n ≥ 0)}
L2= Complement (L1)
Choose appropriate options regarding languages L1 and L2

A. L1& L2 are context free
B. L1 is CFL but L2 is RL
C. L1 is CFL and L2 is CSL
D. None
Solution: Option B
16. The language L= { aNbN/ 0< N < 327th Prime number } is
A. Regular B. Not context sensitive C. Not recursive D. None
Solution: Option A
3
17. Let ∑= {0, 1}
What will be the number of states in minimal DFA, if the Binary number string is congruent
to (mod 8).
A. 8 B. 9 C. 7 D. 4
Solution: Option D
18.
The FA above recognizes a set of stings of length 6, what is the total number of strings that can
be generated from the FA?
A. 18 B. 20 C. 130 D. None.
Solution: Option B
19. What are the number of final states in minimal DFA, where ∑= {a, b}, if every string starts
with “aa” and length of string is not congruent to 0 (mod 4).
A. 7 B. 6 C. 3 D. 5
Solution: Option C
20. How many DFA with four states can be constructed over the alphabet ∑= {a, b} with
designated initial state?
A. 416 * 24 B. 220 C. 216 D. 224
Solution: Option B
21. Let ∑= {a}, assume language, L= { a2012.K/ K> 0}, what is minimum number of states
needed in a DFA to recognize L?
A. 22012 + 1 B. 2013 C. 22013 D. None
4
Solution: Option B
22. The following CFG,
SaB/ bA
A a/ aS/ bAA
B b/ bS/ aBB generates strings with
A. Odd number of a's & odd number of b’s

B. Even number of a's & even number of b's
C. Equal number of a’s & b’s
D. Odd number of a’s & even number of b’s
Solution: Option C
23. Let A= (a + b)* ab (a + b)*, B= a*b* and C= (a + b)*. Then the relation between A, B and C:
A. A+B= C B. AR+BR= C C. AR+B= C D. None
Solution: Option C
24. What type of grammar is this most accurately described as?

S b/ aD
D a/ aDD
A. A regular grammar B. CFG C. CSG D. Type-0
Solution: Option B
25.
Let M1 be the NFA obtained by interchanging final and non-final states of M. Let the
language accepted by M be L and that accepted by M1 be L1. Choose correct statement:
A. L1= L
5
B. L1∩ L2= Φ
C. L1⊆ L2
D. L1= (0+ε)*
Solution: Option D
26. Assertion (a): The language L= Set of all strings not containing 101 as a substring is regular set
Regular (r): L satisfies the regular set but not the pumping lemma.
A. Both (a) and (r) are true and (r) is a reason for (a)
B. Both (a) and (r) are true and (r) is not correct reason (a)
C. Both (a) and (r) are false
D. (a) is true but (r) is false
Solution: Option B
27. Let M= (Q, ∑, δ, S, F) and M’= (Q, ∑, δ, S, Q-F ) where M accepts L and M’ accepts L1 and
M is NFA, what could be the relation between L and L’ ?
A. L and L’ are complement to each other

B. L and L’ are similar to each other
C. L and L’ relation cannot be predicted
D. None of the above
Solution: Option C
COMMON DATA QUESTIONS: Q.28, Q.29 AND Q.30, Q.31
28.
The DFA above accepts:

A. The set of all strings containing two consecutive 1’s
B. (0+1)*
C. Set of all strings not containing two consecutive 1’s
D. Set of all strings containing two consecutive 0’s
Solution: Option B
6
29. The minimal DFA of the above machine has:
A. 1 State B. 5 States C. 3 States D. 2 States
Solution: Option A
Consider the grammar given below where the flowers are non-terminals and animals are
terminals:
X XX/ aX/ bX/ null string
where, a is tiger and b is for lion
30. The grammar generates
A. twice as many tigers as lions

B. any number of tigers and lions
C. more tigers than lions
D. unequal number of tigers and lions
Solution: Option B
31. The string for which the grammar has maximum of two derivation trees is:
A. lion tiger lion B. lion tiger C. tiger lion D. None of the above
Solution: Option D
LINKED ANSWER QUESTIONS: Q.32 & Q.33
32. Consider TM:
If input string is 1000, what will be the output?
A. 1100 B. 1000 C. 0111 D. None
Solution: Option B
7
33. What will be this TM?
A. prints the given input

B. prints the 1’s complement of input given
C. prints the 2’s complement of input given
D. None
Solution: Option C

Theory of Computation Solutions

Uploaded by

Copyright:

Available Formats

Theory of Computation Solutions

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Theory of Computation Solutions

Uploaded by

Copyright:

Available Formats

THEORY OF COMPUTATION

1. Number of trivial substrings in “GATE2013” are:

3. The total number of substrings present in “GATE” is:

5. A minimal DFA that is equivalent to a NDFA has:

A. Always more states B. Always less no. of states

6. Consider following Regular Expression:

What is length of shortest string which is in both (i) & (ii)?

Choose incorrect statement?

A. aabbb can be derived from above grammar

A. (a* + b*a*)* B. (a*b* + b*a*)* (a*b*)*

9. The complement of CFL:

A. Recursive B. Recursive enumerated

10. The language of primes in unary is:

The production missing is

1000000000000000000000000000 states, over the input alphabet consisting of all Greek

A. It is not possible that it accepts the empty set.

14. Consider the grammar:

A. abab B. aabb C. bbaa D. aaabbb

15. Consider the following languages:

Choose appropriate options regarding languages L1 and L2

16. The language L= { aNbN/ 0< N < 327th Prime number } is

A. Regular B. Not context sensitive C. Not recursive D. None

A. 416 * 24 B. 220 C. 216 D. 224

A. 22012 + 1 B. 2013 C. 22013 D. None

22. The following CFG,

A. Odd number of a's & odd number of b’s

A. A+B= C B. AR+BR= C C. AR+B= C D. None

24. What type of grammar is this most accurately described as?

A. A regular grammar B. CFG C. CSG D. Type-0

A. L and L’ are complement to each other

COMMON DATA QUESTIONS: Q.28, Q.29 AND Q.30, Q.31

The DFA above accepts:

A. 1 State B. 5 States C. 3 States D. 2 States

30. The grammar generates

A. twice as many tigers as lions

LINKED ANSWER QUESTIONS: Q.32 & Q.33

32. Consider TM:

If input string is 1000, what will be the output?

A. 1100 B. 1000 C. 0111 D. None

A. prints the given input

You might also like

A. (a* + ba)* B. (ab + ba)* (ab)*