Sets of Set-Equations Equivalent to Context-Free Grammars and Their Solution in Some Cases.
Abstract
Any language defined by a regular context-free grammar can alternately be described by a regular expression. One way in which this is shown is to view the grammar as a set of set equations and to show how the 'solution' of these equations can always be given as a regular expression. Any context-free grammar can be viewed as a set of set equations and the 'solution' of this set is, with some minor qualifications, demonstrated to be the language generated by the grammar. However, in general one does not know a compact notation comparable to that of regular expressions for representing this solution. Nevertheless, such a solution is given for a class of grammars which properly include regular grammars, namely linear grammars. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1971
- Accession Number
- AD0732227
Entities
People
- Marvin C. Paull
Organizations
- Rutgers University Department of Computer Science