
Accession Number : AD0732227
Title : Sets of SetEquations Equivalent to ContextFree Grammars and Their Solution in Some Cases.
Descriptive Note : Technical rept.,
Corporate Author : RUTGERS  THE STATE UNIV NEW BRUNSWICK N J DEPT OF COMPUTER SCIENCE
Personal Author(s) : Paull,Marvin C.
Report Date : JUN 1971
Pagination or Media Count : 13
Abstract : Any language defined by a regular contextfree 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 contextfree 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)
Descriptors : (*CONTEXT FREE GRAMMARS, SET THEORY), (*COMPUTATIONAL LINGUISTICS, CONTEXT FREE GRAMMARS), EQUATIONS
Subject Categories : Linguistics
Distribution Statement : APPROVED FOR PUBLIC RELEASE