Difficulty Generating Factors for Context-free Language Construction Assignments

• URL: http://arxiv.org/abs/2508.01735v1
• Date: Sun, 03 Aug 2025 12:23:04 GMT
• Title: Difficulty Generating Factors for Context-free Language Construction Assignments
• Authors: Florian Schmalstieg, Marko Schmellenkamp, Jakob Schwerter, Thomas Zeume,
• Abstract summary: We investigate factors that influence the difficulty of constructing context-free grammars and pushdown automata for context-free languages.<n>We conducted a controlled experiment using within-subject randomization in an interactive learning system.<n>The results lay foundations for learning systems that adaptively choose appropriate exercises for individual students.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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. 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 targeting how a language is presented to students: representation in natural language and as a verbose set notation. Furthermore, we propose two factors targeting the structure of the given context-free language: nesting of constructs and insertion of multiplicities. 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. The findings for pushdown automata tasks differed markedly from those for context-free grammar tasks. Our variations either had negligible effects or, in some cases, even reduced difficulty. Thus, no robust statistical conclusions can be made for pushdown automata tasks. The results lay foundations for learning systems that adaptively choose appropriate exercises for individual students.

Related papers

• Language Mixing in Reasoning Language Models: Patterns, Impact, and Internal Causes [49.770097731093216]
  Reasoning language models (RLMs) excel at complex tasks by leveraging a chain-of-thought process to generate structured intermediate steps.<n> Language mixing, i.e., reasoning steps containing tokens from languages other than the prompt, has been observed in their outputs and shown to affect performance.<n>We present the first systematic study of language mixing in RLMs, examining its patterns, impact, and internal causes across 15 languages.
  arXiv  Detail & Related papers  (2025-05-20T18:26:53Z)
• Reading Between the Lines: A dataset and a study on why some texts are tougher than others [0.20482269513546458]
  Our research aims at better understanding what makes a text difficult to read for specific audiences with intellectual disabilities.<n>We introduce a scheme for the annotation of difficulties based on empirical research in psychology.<n>We fine-tuned four different pre-trained transformer models to perform the task of multiclass classification.
  arXiv  Detail & Related papers  (2025-01-03T13:09:46Z)
• Integrating Natural Language Prompting Tasks in Introductory Programming Courses [3.907735250728617]
  This report explores the inclusion of two prompt-focused activities in an introductory programming course. The first requires students to solve computational problems by writing natural language prompts, emphasizing problem-solving over syntax. The second involves students crafting prompts to generate code equivalent to provided fragments, to foster an understanding of the relationship between prompts and code.
  arXiv  Detail & Related papers  (2024-10-04T01:03:25Z)
• Simple Linguistic Inferences of Large Language Models (LLMs): Blind Spots and Blinds [59.71218039095155]
  We evaluate language understanding capacities on simple inference tasks that most humans find trivial. We target (i) grammatically-specified entailments, (ii) premises with evidential adverbs of uncertainty, and (iii) monotonicity entailments. The models exhibit moderate to low performance on these evaluation sets.
  arXiv  Detail & Related papers  (2023-05-24T06:41:09Z)
• Coarse-to-Fine: Hierarchical Multi-task Learning for Natural Language Understanding [51.31622274823167]
  We propose a hierarchical framework with a coarse-to-fine paradigm, with the bottom level shared to all the tasks, the mid-level divided to different groups, and the top-level assigned to each of the tasks. This allows our model to learn basic language properties from all tasks, boost performance on relevant tasks, and reduce the negative impact from irrelevant tasks.
  arXiv  Detail & Related papers  (2022-08-19T02:46:20Z)
• Grounding Hindsight Instructions in Multi-Goal Reinforcement Learning for Robotics [14.863872352905629]
  This paper focuses on robotic reinforcement learning with sparse rewards for natural language goal representations. We first present a mechanism for hindsight instruction replay utilizing expert feedback. Second, we propose a seq2seq model to generate linguistic hindsight instructions.
  arXiv  Detail & Related papers  (2022-04-08T22:01:36Z)
• Analyzing the Limits of Self-Supervision in Handling Bias in Language [52.26068057260399]
  We evaluate how well language models capture the semantics of four tasks for bias: diagnosis, identification, extraction and rephrasing. Our analyses indicate that language models are capable of performing these tasks to widely varying degrees across different bias dimensions, such as gender and political affiliation.
  arXiv  Detail & Related papers  (2021-12-16T05:36:08Z)
• Automatic Generation of Word Problems for Academic Education via Natural Language Processing (NLP) [0.0]
  This thesis proposes an approach to generate diverse, context rich word problems. The proposed approach is proven to be effective in generating valid word problems for mathematical statistics.
  arXiv  Detail & Related papers  (2021-09-27T15:36:19Z)
• Curious Case of Language Generation Evaluation Metrics: A Cautionary Tale [52.663117551150954]
  A few popular metrics remain as the de facto metrics to evaluate tasks such as image captioning and machine translation. This is partly due to ease of use, and partly because researchers expect to see them and know how to interpret them. In this paper, we urge the community for more careful consideration of how they automatically evaluate their models.
  arXiv  Detail & Related papers  (2020-10-26T13:57:20Z)
• Machine learning approach of Japanese composition scoring and writing aided system's design [0.0]
  A composition scoring system can greatly assist language learners. It can make language leaner improve themselves in the process of output something. Especially for foreign language learners, lexical and syntactic content are usually what they are more concerned about.
  arXiv  Detail & Related papers  (2020-08-26T11:01:13Z)
• How to Probe Sentence Embeddings in Low-Resource Languages: On Structural Design Choices for Probing Task Evaluation [82.96358326053115]
  We investigate sensitivity of probing task results to structural design choices. We probe embeddings in a multilingual setup with design choices that lie in a'stable region', as we identify for English. We find that results on English do not transfer to other languages.
  arXiv  Detail & Related papers  (2020-06-16T12:37:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.