Bracketed context-free languages

✍ Scribed by Seymour Ginsburg; Michael A. Harrison

• Publisher: Elsevier Science
• Year: 1967
• Tongue: English
• Weight: 1012 KB
• Volume: 1
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(67)80003-5

✦ Synopsis

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 L( G1) C_ L( G~) and whether L( Gt) ~ L( G2) is empty are solvable problems for arbitrary bracketed grammars Gt and G2 with the same brackets and same terminals. Finally, bracketed languages are shown to be codes with strong properties.