Accession Number : AD0732227

Title :   Sets of Set-Equations Equivalent to Context-Free 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 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)

Descriptors :   (*CONTEXT FREE GRAMMARS, SET THEORY), (*COMPUTATIONAL LINGUISTICS, CONTEXT FREE GRAMMARS), EQUATIONS

Subject Categories : Linguistics

Distribution Statement : APPROVED FOR PUBLIC RELEASE