PREVIOUS YEAR SOLVED PAPERS - GATE 2017 Shift 1
- Option : B
- Explanation : The given Grammar over Σ = {a, b, c} with S as the start symbol is S → abScT | abcT T→ bT | b The minimum length string generated by the grammar is 1: S→abcT→abcb; hence all variable greater than 1. Other cases S → abScT→ ab abScT cT → ab ab abScT cT cT →........→ (ab)n (cT)n. Here T can generate any number of b’s starting with single b. Hence The language is {(abncbm1cbm2…cbmn | n, m1, m2, ….., mn ≥ 1 }
- Option : B
- Explanation : ∀x(∃yR(x,y)) ⇒ ∃y∃xR(x,y) ∃y∀xR(x,y) ⇒ ∀x∃yR(x,y) ∀x∃yR(x,y) ⇏ ∃y∀xR(x,y) -∃x(∀y - R(x,y)) ⇔ ∀x∃yR(x,y)
- Option : C
- Explanation : Overflow flag indicates an over flow condition for a signed operation. Some points to remember in a signed operation: * MSB is always reserved to indicate sign of the number. * Negative numbers are represented in 2’s – complement. * An overflow results in invalid operation. 2's complement overflow rules: * If the sum of two positive numbers yields a negative result, the sum has- overflowed. * If the sum of two negative number yields a positive result, the sum has overflowed. * Otherwise, the sum has not overflowed. Overflow for signed numbers occurs when the carry-in into the MSB (most significant bit) is not equal to carry-out. Conveniently, an XOR-operation on these two bits can quickly determine if an overflow condition exists. Therefore, ((A7.B7) ⊕ S7 = (A7.B7.S7 + A7.B7.S7) = 1 has overflowed.
- Option : A
- Explanation : V → W,VW → X,Y → V,Y → X,Y → Z (W is extraneous) V → W,V → X,Y → V,Y → X,Y → Z ∴ Y → X is redundant ∴ {V → W,V → X,Y → V,Y → Z}
