Paper

{
  "raw_xml": "<entry>\n    <id>http://arxiv.org/abs/2602.19743v1</id>\n    <title>NILE: Formalizing Natural-Language Descriptions of Formal Languages</title>\n    <updated>2026-02-23T11:42:56Z</updated>\n    <link href='https://arxiv.org/abs/2602.19743v1' rel='alternate' type='text/html'/>\n    <link href='https://arxiv.org/pdf/2602.19743v1' rel='related' title='pdf' type='application/pdf'/>\n    <summary>This paper explores how natural-language descriptions of formal languages can be compared to their formal representations and how semantic differences can be explained. This is motivated from educational scenarios where learners describe a formal language (presented, e.g., by a finite state automaton, regular expression, pushdown automaton, context-free grammar or in set notation) in natural language, and an educational support system has to (1) judge whether the natural-language description accurately describes the formal language, and to (2) provide explanations why descriptions are not accurate.\n  To address this question, we introduce a representation language for formal languages, Nile, which is designed so that Nile expressions can mirror the syntactic structure of natural-language descriptions of formal languages. Nile is sufficiently expressive to cover a broad variety of formal languages, including all regular languages and fragments of context-free languages typically used in educational contexts. Generating Nile expressions that are syntactically close to natural-language descriptions then allows to provide explanations for inaccuracies in the descriptions algorithmically.\n  In experiments on an educational data set, we show that LLMs can translate natural-language descriptions into equivalent, syntactically close Nile expressions with high accuracy - allowing to algorithmically provide explanations for incorrect natural-language descriptions. Our experiments also show that while natural-language descriptions can also be translated into regular expressions (but not context-free grammars), the expressions are often not syntactically close and thus not suitable for providing explanations.</summary>\n    <category scheme='http://arxiv.org/schemas/atom' term='cs.FL'/>\n    <category scheme='http://arxiv.org/schemas/atom' term='cs.CL'/>\n    <category scheme='http://arxiv.org/schemas/atom' term='cs.LO'/>\n    <published>2026-02-23T11:42:56Z</published>\n    <arxiv:primary_category term='cs.FL'/>\n    <author>\n      <name>Tristan Kneisel</name>\n    </author>\n    <author>\n      <name>Marko Schmellenkamp</name>\n    </author>\n    <author>\n      <name>Fabian Vehlken</name>\n    </author>\n    <author>\n      <name>Thomas Zeume</name>\n    </author>\n  </entry>"
}