Computer science students often struggle with abstract theoretical concepts, particularly in introductory courses on theoretical computer science. One such challenge is understanding context-free languages and their various representations, including natural language descriptions, set notation, context-free grammars, and pushdown automata.

In this study we investigate factors that influence the difficulty of constructing context-free grammars and pushdown automata for context-free languages. We propose two potential difficulty generating factors that target variations of how a language is presented to students and two factors that target the structure of the given context-free language. To our knowledge, this is the first study on difficulty-generating factors in exercises on context-free languages within theoretical computer science education.

We conducted a controlled experiment using within-subject randomization in an interactive learning system, testing the proposed difficulty factors for constructing context-free grammars and pushdown automata. Our results suggest that three of the four factors significantly influence students’ objective performance in solving exercises for constructing context-free grammars, while students’ perceived difficulties only partly align with the objective performance measures. For pushdown automata tasks, our results reveal high task-level heterogeneity, introducing high variance in the estimation of the experimentally manipulated difficulty factors. Thus, no robust statistical conclusions can be made for pushdown automata tasks.

The results lay foundations for interactive learning systems that adaptively choose appropriate exercises from this domain for individual students.