A water gap is usually an indication of a river that is older than the current topography. The likely occurrence is that a river established its course when the landform was at a low elevation, or by a rift in a portion of the crust of the earth having a very low stream gradient and a thick layer of unconsolidated sediment.
In a hypothetical example, a river would have established its channel without regard for the deeper layers of rock. A later period of uplift would cause increased erosion along the riverbed, exposing the underlying rock layers. As the uplift continued, the river, being large enough, would continue to erode the rising land, cutting through ridges as they formed.