PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2017 Shift 1
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 }
∀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)
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.
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}
