Logic as a knowledge representation and reasoning language is a fundamental topic of an Artificial Intelligence (AI) course and includes a number of sub-topics. One of them, which brings difficulties to students to deal with, is converting natural language (NL) sentences into first-order logic (FOL) formulas. To assist students to overcome those difficulties, we developed the NLtoFOL system and equipped it with a strong assistance and feedback mechanism. In this work, first, we present that feedback mechanism. The mechanism can provide assistance before an answer is submitted, if requested, but mainly it provides assistance after an answer is submitted. To that end, it characterizes the answer in terms of completeness and accuracy to determine the level of incorrectness, based on an answer categorization scheme, introduced in this paper. The automatically generated natural language feedback sequences grow from general to specific and can include statements on a student’s metacognitive state. Feedback is provided as natural language sentences automatically generated through a template-based natural language generation mechanism. Second, we present an extensive evaluation of the effectiveness of the assistance and feedback mechanism on students’ learning. The evaluation of feedback with students showed that full feedback sequences lead to greater learning gains than sequences consisting of only flag feedback and bottom-out hints (n = 226), and that generic, template-based feedback sequences are comparable to the utility of problem-specific hints generated by human tutors (n = 120).