Choose the best classifier to predict the label of strings of a regular language
My bet would go to a Recurrent Neural Network, as it closely models some (fuzzy, non-discrete) state machine as each character is output. A decent start to read up on RNNs for this purpose is to read the article The Unreasonable Effectiveness of Recurrent Neural Networks which describes character-level RNNs used to predict text.