NILE: Formalizing Natural-Language Descriptions of Formal Languages

• URL: http://arxiv.org/abs/2602.19743v1
• Date: Mon, 23 Feb 2026 11:42:56 GMT
• Title: NILE: Formalizing Natural-Language Descriptions of Formal Languages
• Abstract 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.<n>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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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. 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. 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.

Related papers

• Symbolic Informalization: Fluent, Productive, Multilingual [0.0]
  Symbolic informalization enables a reliable conversion of formal mathematics to natural language.<n>This paper outlines the project Informath, which aims to show how symbolic informalization can produce fluent text.
  arXiv  Detail & Related papers  (2026-06-15T16:06:21Z)
• Coherency through formalisations of Structured Natural Language, A case study on FRETish [0.0]
  Formalisation is the process of writing system requirements in a formal language.<n>In this paper we propose a new guideline: Coherency through Formalisations.<n>We analyze NASA's Formal Requirement Elicitation Tool FRET and propose an alternative automated translation of the Controlled Natural Language FRETish to the formal language of MTL.
  arXiv  Detail & Related papers  (2026-05-11T12:30:53Z)
• Evaluating In-Context Translation with Synchronous Context-Free Grammar Transduction [17.60599688606413]
  Low-resource languages pose a challenge for machine translation with large language models (LLMs)<n>We construct synchronous context-free grammars which define pairs of formal languages.<n>We measure how well LLMs can translate sentences from one formal language into another when given both the grammar and the source-language sentence.
  arXiv  Detail & Related papers  (2026-04-08T17:35:44Z)
• Linguistic Generalizations are not Rules: Impacts on Evaluation of LMs [13.700007279857081]
  Linguistic evaluations of how well LMs generalize often take for granted that natural languages are generated by symbolic rules.<n>Here we suggest that LMs' failures to obey symbolic rules may be a feature rather than a bug.<n>New utterances are produced and understood by a combination of flexible, interrelated, and context-dependent constructions.
  arXiv  Detail & Related papers  (2025-02-18T17:40:20Z)
• DeSTA: Enhancing Speech Language Models through Descriptive Speech-Text Alignment [82.86363991170546]
  We propose a Descriptive Speech-Text Alignment approach that leverages speech captioning to bridge the gap between speech and text modalities. Our model demonstrates superior performance on the Dynamic-SUPERB benchmark, particularly in generalizing to unseen tasks. These findings highlight the potential to reshape instruction-following SLMs by incorporating descriptive rich, speech captions.
  arXiv  Detail & Related papers  (2024-06-27T03:52:35Z)
• How Proficient Are Large Language Models in Formal Languages? An In-Depth Insight for Knowledge Base Question Answering [52.86931192259096]
  Knowledge Base Question Answering (KBQA) aims to answer natural language questions based on facts in knowledge bases. Recent works leverage the capabilities of large language models (LLMs) for logical form generation to improve performance.
  arXiv  Detail & Related papers  (2024-01-11T09:27:50Z)
• Trustworthy Formal Natural Language Specifications [3.8073142980733]
  This paper shows it is possible to build support for specifications written in expressive subsets of natural language. We implement a means to provide specifications in a modularly formal subset of English, and have them automatically translated into formal claims. We produce proof certificates explaining how each word was interpreted and how the sentence's structure was used to compute the meaning.
  arXiv  Detail & Related papers  (2023-10-05T20:41:47Z)
• Language Models as Inductive Reasoners [125.99461874008703]
  We propose a new paradigm (task) for inductive reasoning, which is to induce natural language rules from natural language facts. We create a dataset termed DEER containing 1.2k rule-fact pairs for the task, where rules and facts are written in natural language. We provide the first and comprehensive analysis of how well pretrained language models can induce natural language rules from natural language facts.
  arXiv  Detail & Related papers  (2022-12-21T11:12:14Z)
• Transparency Helps Reveal When Language Models Learn Meaning [71.96920839263457]
  Our systematic experiments with synthetic data reveal that, with languages where all expressions have context-independent denotations, both autoregressive and masked language models learn to emulate semantic relations between expressions. Turning to natural language, our experiments with a specific phenomenon -- referential opacity -- add to the growing body of evidence that current language models do not well-represent natural language semantics.
  arXiv  Detail & Related papers  (2022-10-14T02:35:19Z)
• Formal Specifications from Natural Language [3.1806743741013657]
  We study the ability of language models to translate natural language into formal specifications with complex semantics. In particular, we fine-tune off-the-shelf language models on three datasets consisting of structured English sentences.
  arXiv  Detail & Related papers  (2022-06-04T10:49:30Z)
• AUTOLEX: An Automatic Framework for Linguistic Exploration [93.89709486642666]
  We propose an automatic framework that aims to ease linguists' discovery and extraction of concise descriptions of linguistic phenomena. Specifically, we apply this framework to extract descriptions for three phenomena: morphological agreement, case marking, and word order. We evaluate the descriptions with the help of language experts and propose a method for automated evaluation when human evaluation is infeasible.
  arXiv  Detail & Related papers  (2022-03-25T20:37:30Z)
• Interpreting Language Models with Contrastive Explanations [99.7035899290924]
  Language models must consider various features to predict a token, such as its part of speech, number, tense, or semantics. Existing explanation methods conflate evidence for all these features into a single explanation, which is less interpretable for human understanding. We show that contrastive explanations are quantifiably better than non-contrastive explanations in verifying major grammatical phenomena.
  arXiv  Detail & Related papers  (2022-02-21T18:32:24Z)

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.