# Theory of Computation (Test 5)

## Gate Exam : Cs Computer Science And Information Technology

| Home | | Gate Exam | | Cs Computer Science And Information Technology | | Theory of Computation |

Theory of Computation
| Theory of Computation |
Q.1
Let L = {w ∈ (0 + 1)* | w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expressions below represents L?
A. (0 *10 *1)*
B. 0 * (10 * 10 *) *
C. 0 * (10 * 1 *) * 0 *
D. 0 * 1 (10 * 1) * 10 *
Answer : Option A
Explaination / Solution:
No Explaination.

Workspace
Report
Q.2
Consider the languages L1 = {0i1j | i≠j}. L2 = {0i1j | i=j}. L3 = {0i1j | i=2j+1}. L4 = {0i1j | i≠2j}. Which one of the following statements is true?
A. Only L2 is context free
B. Only L2 and L3 are context free
C. Only L1 and L2 are context free
D. All are context free
Answer : Option A
Explaination / Solution:
No Explaination.

Workspace
Report
Q.3
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.
A. 1 and 4 only
B. 1 and 3 only
C. 2 only
D. 3 only
Answer : Option C
Explaination / Solution:

(1) NTM ≅ DTM
(2) RELs are closed under union & but not complementation
(3) Turing decidable languages are recursive and recursive languages are closed under intersection and complementation
(4) RELs are closed under union & intersection but not under complementation

Workspace
Report
Q.4
Let w be any string of length n in {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?
A. n-1
B. n
C. n+1
D. 2n-1
Answer : Option B
Explaination / Solution:
No Explaination.

Workspace
Report
Q.5
What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e., of type A → ∈ and A → a) to parse a string with n tokens?
A. n/2
B. n-1
C. 2n-1
D. 2n
Answer : Option B
Explaination / Solution:

To have maximum number of reduce moves, all the productions will be of the typeA→αβ (where α and β could be terminals or non-terminals). Consider the following illustration then:

Workspace
Report
Q.6
Consider the languages L= Φ and L= {a} . Which one of the following represents L1 L2* UL1* ?
A. {∈}
B. Φ
C. a *
D. {ε, a}
Answer : Option A
Explaination / Solution:
No Explaination.

Workspace
Report
Q.7
Which of the following is/are undecidable?
1. G is a CFG. Is L (G) = Φ?
2. G is a CFG. IS L (G) =  Σ*?
3. M is a Turning machine. Is L(M) regular?
4. A is a DFA and N is a NFA. Is L (A) = L (N) ?
A. 3 only
B. 3 and 4 only
C. 1, 2 and 3 only
D. 2 and 3 only
Answer : Option D
Explaination / Solution:

There is an algorithm to check whether the given CFG is empty, finite or infinite and also to convert NFA to DFA hence 1 and 4 are decidable

Workspace
Report
Q.8
Consider the following two sets of LR(1) items of an LR(1) grammar
X → c.X, c / d    X → c.X, \$
X → .cX, c / d    X → .cX, \$
X → .d, c / d      X → .d, \$
Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE?
1. Cannot be merged since look aheads are different
2. Can be merged but will result in S–R conflict
3. Can be merged but will result in R–R conflict
4. Cannot be merged since goto on c will lead to two different sets

A. 1 only
B. 2 only
C. 1 and 4 only
D. 1, 2, 3 and 4
Answer : Option D
Explaination / Solution:

1. Merging of two states depends on core part (production rule with dot operator), not on look aheads.
2. The two states are not containing Reduce item ,So after merging, the merged state can not contain any S-R conflict
3. As there is no Reduce item in any of the state, so can’t have R-R conflict.
4. Merging of stats does not depend on further goto on any terminal. So all statements are false.

Workspace
Report
Q.9
Consider the DFA given below.

Which of the following are FALSE?
1. Complement of L(A) is context–free
2. L(A) = L ((11*0+0)(0+1)*0*1*)
3. For the language accepted by A, A is the minimal DFA
4. A accepts all strings over {0, 1} of length at least 2
A. 1 and 3 only
B. 2 and 4 only
C. 2 and 3 only
D. 3 and 4 only
Answer : Option D
Explaination / Solution:

(1) L(A) is regular, its complement is also regular and if it is regular it is also context free.
(2) L(A) = (11*0+0)(0+1)*0*1* = 1*0(0+1)* Language has all strings where each string contains ‘0’.
(3) A is not minimal, it can be constructed with 2 states
(4) Language has all strings, where each string contains ‘0’. (atleast length one)

Workspace
Report
Q.10
Consider the following languages

Which one of the following statements is FALSE?
A. L2 is context–free
B. L1 ∩ Lis context–free
C.  Complement of L2  is recursive
D. Complement of L1 is context–free but not regular
Answer : Option D
Explaination / Solution:

Workspace
Report