Accession Number:

AD0631337

Title:

BRACKETED CONTEXT FREE LANGUAGES.

Descriptive Note:

Corporate Author:

SYSTEM DEVELOPMENT CORP SANTA MONICA CALIF

Report Date:

1966-01-04

Pagination or Media Count:

38.0

Abstract:

A bracketed grammar is a context free grammar in which indexed brackets are inserted around the right-hand sides of the rules. The language generated by a bracketed grammar is a bracketed language. An algebraic condition is given for one bracketed language to be a subset of another. The intersection and the difference of two bracketed languages with the same brackets and terminals are context free although not necessarily bracketed languages. Whether LG1 is a subset of LG2 and whether the intersection of LG1 with LG2 is empty are solvable problems for arbitrary bracketed grammars G1 and G2 with the same brackets and same terminals. Bracketed languages are shown to be codes with strong properties. Author

Subject Categories:

  • Linguistics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE