The use of temporal context in the generation of strings

Du Toit, Christine (2002-03)

Thesis (MSc)--Stellenbosch University , 2002.

Thesis

ENGLISH ABSTRACT: Grammars with regulated rewriting are used to restrict the application of contextfree productions in order to avoid certain derivations. This enables these grammars to generate both context-free and non-context-free languages using only production rules with a context-free format. These grammars are more powerful than contextfree grammars, but usually not as powerful as context-sensitive grammars. Various grammars with regulated rewriting have been developed and some will be discussed in this thesis. Propositional linear temporal logic is a formal system used to describe truth values of propositions over time. This is done by defining a timeline together with a set of propositions. It is then possible to construct temporal logic formulae, consisting of these propositions and temporal operators, to specify the truth values of the propositions for every step in the timeline. In this thesis we define and discuss temporal grammars that combine grammars with propositionallinear temporal logic. Since a derivation can be associated with a timeline, a regulating device can be constructed from temporal logic formulae, that will control the application of productions within the derivation. The discussion on temporal grammars includes some of the properties of these grammars, while many ideas are illustrated by examples.

AFRIKAANSE OPSOMMING: Grammatikas met gereguleerde herskrywing word gebruik om 'n beperking te plaas op die toepassing van konteksvrye produksies en verhoed sodoende sekere afleidings. Hierdie grammatikas beskik oor die vermoe om beide konteksvrye en nie-konteksvrye tale te genereer deur slegs produksiereels van 'n konteksvrye formaat te gebruik. Grammatikas met gereguleerde herskrywing is dus sterker as konteksvrye grammatikas, alhoewel dit soms swakker as konteks-sensitiewe grammatikas is. 'n Verskeidenheid sulke grammatikas is al ontwikkel en sommige sal in hierdie tesis bespreek word. Proposisionele lineere temporale logika is 'n formele stelsel wat gebruik kan word om die waarheidswaardes van proposisies oor tyd te beskryf. Dit word gedoen deur 'n tydlyn, asook 'n versameling proposisies te definieer. Dit is clan moontlik om temporale operatore tesame met die proposisies te gebruik om temporale logika-formules te konstrueer wat in staat is om waarheidswaardes van die proposisies te spesifiseer vir elke oomblik in die tydlyn. In hierdie tesis word temporale grammatikas, wat grammatikas met proposisionele lineere temporale logika kombineer, gedefinieer en bespreek. Aangesien 'n afleiding met 'n tydlyn geassosieer kan word, is dit moontlik om 'n regulerende meganisme uit temporale logika-formules te konstrueer wat die toepassing van produksiereels in die afleiding kontroleer. Die bespreking van temporale grammatikas sluit 'n verskeidenheid eienskappe van die grammatikas in, asook 'n aantal voorbeelde wat ter illustrasie gebruik word.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/53183
This item appears in the following collections: