Spelling suggestions: "subject:"anormal languages"" "subject:"9normal languages""
1 
Ogden's lemma for random permitting and forbidding context picture languages and tabledriven contextfree picture languagesIdahosa, Joy O 06 May 2015 (has links)
A dissertation submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in fulfilment of requirements for the degree of Master of Science. Johannesburg, February 16, 2015. / Random context picture grammars are used to generate pictures through successive refinement.
There are three important subclasses of random context picture grammars, namely random permitting
context picture grammars, random forbidding context picture grammars and tabledriven
contextfree picture grammars. These grammars generate the random permitting context picture
languages, random forbidding context picture languages and tabledriven contextfree picture
languages, respectively. Theorems exist which provide necessary conditions that have to be
satisfied by a language before it can be classified under a particular subclass. Some of these
theorems include the pumping and shrinking lemmas, which have been developed for random
permitting context picture languages and random forbidding context picture languages respectively.
Two characterization theorems were developed for the tabledriven contextfree picture
languages.
This dissertation examines these existing theorems for picture languages, i.e., the pumping
and shrinking lemmas and the two characterisation theorems, and attempts to prove theorems,
which will provide an alternative to the existing theorems and thus provide new tools for identifying
languages that do not belong to the various classes. This will be done by adapting Ogden’s
idea of marking parts of a word which was done for the string case. Our theorems essentially involve
marking parts of a picture such that the pumping operation increases the number of marked
symbols and the shrinking operation reduces it.

2 
On contextfree derivationsMäkinen, Erkki. January 1985 (has links)
Thesis (Ph. D.)University of Tampere, 1985. / Includes bibliographical references (p. 9194).

3 
Some combinatorial and algebraic problems related to subwordsPéladeau, Pierre. January 1986 (has links)
No description available.

4 
Desátomat  aplikace pro názornou výuku problematiky formálních gramatikDusíková, Hana January 2011 (has links)
No description available.

5 
Some combinatorial and algebraic problems related to subwordsPéladeau, Pierre. January 1986 (has links)
No description available.

6 
A survey of Greibach normal form : transformation & analysis /Ho, Man Chi. January 2006 (has links)
Thesis (M.Phil.)Hong Kong University of Science and Technology, 2006. / Includes bibliographical references (leaves 4950). Also available in electronic version.

7 
Knowledge representation in mathematics : a case study in graph theory /Epstein, Susan Lynn. January 1983 (has links)
Thesis (Ph. D.)Rutgers University, 1983. / Includes bibliographical references (p. 271274).

8 
Some results on systolic tree automata as acceptorsFoufa, Aouaouche Fazileit January 1985 (has links)
No description available.

9 
Applications of algebraic automata theory to quantum finite automataMercer, Mark. January 2007 (has links)
No description available.

10 
Languages Generated by Iterated Idempotencies.Leupold, KlausPeter 22 November 2006 (has links)
The rewrite relation with parameters m and n and with the possible length limit = k or :::; k we denote by w~, =kW~· or ::;kw~ respectively. The idempotency languages generated from a starting word w by the respective operations are wD<l::', w=kD<l::' and W<;kD<l::'.Also other special cases of idempotency languages besides duplication have come up in different contexts. The investigations of Ito et al. about insertion and deletion, Le., operations that are also observed in DNA molecules, have established that w5 and w~ both preserve regularity.Our investigations about idempotency relations and languages start out from the case of a uniform length bound. For these relations =kW~ the conditions for confluence are characterized completely. Also the question of regularity is k n answered for aH the languages w D<lm . They are nearly always regular. Only the languages wD<lo for n > 1 are more complicated and belong to the class of contextfree languages.For a generallength bound, i.e."for the relations :"::kW~, confluence does not hold so frequently. This complicatedness of the relations results also in more complicated languages, which are often nonregular, as for example the languages W<;kD<l::' for aH bounds k 2 4. For k :::; 2 they are regular. The case of k :::; 3, though, remains open. We show, however, that none of these languages ever exceeds the complexity of being contextfree.Without any length bound, idempotency relations have a very complicated structure. Over alphabets of one or two letters we still characterize the conditions for confluence. Over three or more letters, in contrast, only a few cases are solved. We determine the combinations of parameters that result in the regularity of wD<l::', when the alphabet of w contains only two letters. Only the case of 2 :::; m < n remains open.In a second chapter sorne more involved questions are solved for the special case of duplication. First we shed sorne light on the reasons why it is so difficult to determine the contextfreeness ofduplication languages. We show that they fulfiH aH pumping properties and that they are very dense. Therefore aH the standard tools to prove noncontextfreness do not apply here.The concept of root in Formal Language ·Theory is frequently used to describe the reduction of a word to another one, which is in sorne sense elementary.For example, there are primitive roots, periodicity roots, etc. Elementary in connection with duplication are squarefree words, Le., words that do not contain any repetition. Thus we define the duplication root of w to consist of aH the squarefree words, from which w can be reached via the relation w~.Besides sorne general observations we prove the decidability of the question, whether the duplication root of a language is finite.Then we devise acode, which is robust under duplication of its code words.This would keep the result of a computation from being destroyed by dupli cations in the code words. We determine the exact conditions, under which infinite such codes exist: over an alphabet of two letters they exist for a length bound of 2, over three letters already for a length bound of 1.Also we apply duplication to entire languages rather than to single words; then it is interesting to determine, whether regular and contextfree languages are closed under this operation. We show that the regular languages are closed under uniformly bounded duplication, while they are not closed under duplication with a generallength bound. The contextfree languages are closed under both operations.The thesis concludes with a list of open problems related with the thesis' topics.

Page generated in 0.1258 seconds