Regularly Controlled Bidirectional Extended Linear Basic Grammars (Revised and extended version)

Share/Save/Bookmark

Hogendorp, Jan Anne (1989) Regularly Controlled Bidirectional Extended Linear Basic Grammars (Revised and extended version). [Report]

[img]
Preview
PDF
151Kb
Abstract:We study the concept of bidirectional application of productions - i.e., using a production of a grammar as a reduction too - with respect to regularly controlled extended linear basic (macro) grammars [3], provided with a restricted mode of derivation. So this new grammatical model is in essence equal to the regularly controlled bidirectional context-free grammar of [15] in which the underlying context-free grammar is replaced by an extended linear basic grammar. We establish closure properties of the corresponding family of languages; viz. for the outside-in or OI mode we obtain a full substitution-closed AFL, and for the inside-out or IO mode we obtain a full QAFL closed under deterministic substitution. The notion of bidirectionality gives rise to a dramatic increase of generating power; even under minor assumptions the OI [IO] instance of such grammars generate all OI-macro [IO-macro, respectively] languages. Furthermore, in case of free application of productions and reductions we obtain a generating capacity equal to the one of phrase-structure grammars.
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/64295
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page