Thesis (MSc)--Stellenbosch University , 2002. / 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.
Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/53183 |
Date | 03 1900 |
Creators | Du Toit, Christine |
Contributors | Van Der Walt, A. P. J ., Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. |
Publisher | Stellenbosch : Stellenbosch University |
Source Sets | South African National ETD Portal |
Language | en_ZA |
Detected Language | Unknown |
Type | Thesis |
Format | 42 p. |
Rights | Stellenbosch University |
Page generated in 0.0156 seconds