ScholarLens Back to search
1984•ACM SIGCSE BulletinRequires access

A formal method for determining if a grammar is connected and grounded

David S. Burris

Open publisher page 0 citations

Abstract

This paper introduces a formal method for determining if the production rules in a regular or context free grammar are "connected" (can appear in a sentential form) and "grounded" (can be driven to a string of terminal symbols). I have used it on several occasions in courses on programming language design or language translator implementation to verify that proposed student grammars were reduced (connected and grounded). The technique is also useful for reviewing matrix algebra and the theory of relations with students. The student must know or be introduced to Warshall's algorithm for generating the transitive closure of a relation [1--4].

About this research paper

What this paper is about

This paper introduces a formal method for determining if the production rules in a regular or context free grammar are "connected" (can appear in a sentential form) and "grounded" (can be driven to a string of terminal symbols). I have used it on several occasions in courses on programming language design or language translator implementation to verify that proposed student grammars were reduced (connected and grounded). The technique is also useful for reviewing matrix algebra and the theory of relations with students. The student must know or be introduced to Warshall's algorithm for generating the transitive closure of a relation [1--4].

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

This paper introduces a formal method for determining if the production rules in a regular or context free grammar are "connected" (can appear in a sentential form) and "grounded" (can be driven to a string of terminal symbols). I have used it on several occasions in courses on programming language design or language translator implementation to verify that proposed student grammars were reduced (connected and grounded). The technique is also useful for reviewing matrix algebra and the theory of relations with students. The student must know or be introduced to Warshall's algorithm for generating the transitive closure of a relation [1--4].

Key concepts: Transitive closure, Formal grammar, Regular grammar, Computer science, Grammar systems theory, Grammar, Grounded theory, Transitive relation

Related papers

Related paper 1Related paper 2
Back to paper searchBrowse research topicsOriginal source
A formal method for determining if a grammar is connected and grounded — Research Paper | ScholarLens