Is it possible to have a validation error less than train error for a while followed by the reverse behaviour?
The behavior you notice in the graphs will always be the case regardless of the machine learning algorithm. Machine learning will require you to fit some parameters such that the model can capture the mappings from your input space to the desired outputs. 

At the start of the training these parameters will all be assigned randomly, thus we should assume random performance, thus 50% for a 0/1 classification. As the model parameters are tuned using the training data, the model will tend to decrease both the training and evaluation loss. However, after some training there will be a point where the evaluation loss starts increasing. This is the point where the parameters are no longer generalizing for the data but is instead overfitting and specifically identifying points in the training data. 

This is NOT what we want. This is overfitting. We want to stop the training at the minimum loss of the evaluation set. 



Another way to think of this is if I ask a child to look through some multiplication examples, 

3*2 = 6 
4*3 = 12
...
...
10*1= 10

If the kid learns some general rules as to how x*y=z then he will be able to answer any new multiplication question I ask him. However, if he just memorizes the outcomes of the few examples that I showed them then they will get any new instance wrong. This is overfitting. 



As another example, imagine fitting a 2nd order relationship between 2 variables with a 5th order polynomial. This will match the points too specifically and will not generalize to new data.