# June 2014 Paper 2 (Page 1 of 5)

1. Infrared signals can be used for short range communication in a closed area using ………………. propagation.
(A) ground (B) sky
(C) line of sight (D) space

Answer: C Explanation: Wireless Transmission is of three types – Radio wave, Microwave and Infrared. (A) Physical (B) Network

Answer: A Explanation: A function of a Bridge takes place in the Data Link layer that means it cannot read IP address. It can only read the outermost hardware address that is contained in the Ethernet data.

3. The minumum frame length for 10 Mbps Ethernet is _________ bytes and maximum is _________ bytes.
(A) 64 & 128 (B) 128 & 1518
(C) 1518 & 3036 (D) 64 & 1518

Explanation: 4. The bit rate of a signal is 3000 bps. If each signal unit carries 6 bits, the baud rate of the signal is _________.
(A) 500 bauds/sec (B) 1000 bauds/sec
(C) 1000 bauds/sec (D) 3000 bauds/sec

Explanation:
Bit rate [related to digital signal]: Number of bits per unit time
Baud rate [related to analog signal]: Number of signal elements or signal units [cycles in analog signal] per unit time
“Each signal unit carries 6 bits” means one cycle when converted to digital form yields 6 bits.
So, 6 bits per second pass means 1 signal unit passes.
Then, 3000 bits per second pass means 3000/6 = 500 signal units pass per second. That is, 500 bauds per second pass that means the Baud rate is 500.

5. Match the following:
List – I List – II
a. Physical Layer i. Allow resources to network access
b. Datalink Layer ii. Move packets from one destination to other
c. Network Layer iii. Process to process message delivery
d. Transport Layer iv. Transmission of bit stream
e. Application Laye v. Formation of frames
Codes:
a b c d e
(A) iv v ii iii i
(B) v iv i ii iii
(C) i iii ii v iv
(D) i ii iv iii v

Explanation:
Physical Layer: The layer outside the system where NIC (Network Interface Card) draws raw bits in electrical form and conveys them to the medium.
ensures initial connection establishment
splits stream of data into frames
handles the acknowledgements from a receiver
ensures error free data
arranges the packets sequentially

Network Layer: This layer
sets up logical connection
forwards data from one node to another
routes data packets selecting the best route using efficient algorithms
delivers error reports
Transport Layer: This layer
detect errors and lost data
recovers lost data
manages retransmission of data
transmits messages between processes in details
Application Layer: This layer manages data of the applications (like email, file transfer, Telnet etc.) initiated by the users at one computer to be transferred to another.

6. A grammar G is LL(1) if and only if the following conditions hold for two distinct productions A → α | β
I. First (α) ∩ First (β) ≠ {a} where a is some terminal symbol of the grammar.
II. First (α) ∩ First (β) ≠ λ
III. First (α) ∩ Follow(A) = φ if λ є First (β)

(A) I and II (B) I and III
(C) II and III (D) I, II and III

Explanation:
Condition 1: If both the FIRSTs produce a, then there is ambiguity and breaks the definition of LL(1). If this condition is not satisfied, then any token in FIRST(a) ∩ FIRST(β) will fail to tell us which right-hand side to choose.
Condition 2: The FIRSTs should not produce empty string.
Condition 3: If this condition is not satisfied, then any token in FIRST(β) ∩ FOLLOW(A) will fail to tell us whether to choose β or є.
A context-free grammar G = (VT, VN, S, P) whose parsing table has no multiple entries i.e., the grammar must not be left recursive and the rule which should be chosen when developing a non-terminal must be determined by that non-terminal and the (at most) next token on the input (non-ambiguous) is said to be LL(1).
In LL(1), the first L stands for scanning the input from left to right, the second L stands for producing a leftmost derivation and the 1 stands for using one input symbol of look-ahead at each step to make parsing action decision.
The rules for finding FIRST sets:
To compute FIRST(X) for all grammar symbols X, apply the following rules until no more terminals or e can be added to any FIRST set:
1. If X is terminal, then FIRST(X) is {X}.
2. If X -→ e is a production, then add e to FIRST(X).
3. If X is non-terminal and X -→ Y1 Y2 … Yk . is a production, then place a in FIRST(X) if for some i, a is in FIRST(Yi ), and Ԑ is in all of FIRST(Y1), … , FIRST(Yi-1); that is, Y1, … ,Yi-1 => Ԑ. If Ԑ is in FIRST(Yj ) for all j = 1, 2, … , k, then add Ԑ to FIRST(X). For example, everything in FIRST(Y1) is surely in FIRST(X). If Y1 does not derive Ԑ, then we add nothing more to FIRST(X), but if Y1 -→ Ԑ, then we add FIRST(Y2) and so on.
The rules for finding FOLLOW sets:
First put \$ (the end of input marker) in Follow(S) (S is the start symbol)
If there is a production A → aBb, (where a can be a whole string) then everything in FIRST(b) except for ε is placed in FOLLOW(B).
If there is a production A → aB, then everything in FOLLOW(A) is in FOLLOW(B)
If there is production A → aBb, where FIRST(b) contains ε, then everything in FOLLOW(A) is in FOLLOW(B)

7. Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?
(A) Removing left recursion alone
(B) Removing the grammar alone
(C) Removing left recursion and factoring the grammar
(D) None of the above

Explanation:
To convert a CFG to LL(1) grammar, the following conditions must be satisfied:
For every pair of productions A → α | β
I. FIRST(α) ∩ FIRST(β) = ɸ
and if FIRST(β) contains ε, and FIRST(α) does not contain ε, then
FIRST(α)∩ FOLLOW(A) = ɸ
II. First (α) ∩ First (β) ≠ λ
III. First (α) ∩ Follow(A) = φ if λ є First (β)

8. A shift reduce parser suffers from
(A) shift reduce conflict only
(B) reduce reduce conflict only
(C) both shift reduce conflict and reduce reduce conflict
(D) shift handle and reduce handle conflicts

Explanation: An LR parser may encounter two types of conflicts: shift-reduce conflicts and reduce-reduce conflicts. AShift-Reduce error is caused when the grammar allows a rule to be reduced for particular token, but, at the same time, allowing another rule to be shifted for that same token. As a result, the grammar is ambiguous since a program can be interpreted more than one way. This error is often caused by recursive grammar definitions where the system cannot determine when one rule is complete and another is just started.
A Reduce-Reduce error is caused when a grammar allows two or more different rules to be reduced at the same time, for the same token. When this happens, the grammar becomes ambiguous since a program can be interpreted more than one way. This error can be caused when the same rule is reached by more than one path.

9. The context free grammar for the language L = {anbmck | k=|n-m|, n≥0, m≥0, k≥0} is
(A) S → S1S3, S1 → aS1c | S2 | λ, S2 → aS2b| λ, S3 → aS3b | S2 | λ
(B) S→S1S3, S1→aS1S2c |λ, S2→aS2b|λ, S3→aS3b|S4| λ, S4→bS4c|λ
(C) S→S1|S2, S1→aS1S2c|λ, S2→aS2b|λ, S3→aS3b|S4| λ, S4→bS4c|λ
(D) S→S1|S3, S1→aS1c |S2|λ, S2→aS2b|λ, S3→aS3b|S4| λ, S4→bS4c|λ
(C) S→S1|S2, S1→aS1S2c|λ, S2→aS2b|λ, S3→aS3b|S4| λ, S4→bS4c|λ
(D) S→S1|S3, S1→aS1c |S2|λ, S2→aS2b|λ, S3→aS3b|S4| λ, S4→bS4c|λ

Explanation:
Number of a’s >=0
Number of b’s>=0
Number of c’s>=0 and |a’s – b’s|
Deduce the options to find the correct answer.

10. The regular grammar for the language L = {w | na(w) and nb(w) are both even, w ε {a,b}*} is given by
Assume p, q, r , s are states
(A) p→aq |br|λ, q→bs|ap
r→as|bp, s→ar|bq,
p and s are initial and final states.
(B) p→aq|br, q→bs|ap
r→as|bp, s→ar|bq,
p and s are initial and final states
(C) p→aq|br|λ, q→bs|ap
r→as|bp, s→ar|bq,
p is both initial and final states
(D) p→aq|br, q→bs|ap
r→as|bp, s→ar|bq,
p is both initial and final states.