臺灣博碩士論文加值系統

在電腦科學這領域中，上下文自由格式語言是最實用也是最重要的，而正則語言是上下文自由格式語言中特別的一種。與正則語言相對的，則是析取語言。析取語言和析取序對，是石煇然老師在西元一九九七年首先提出。

析取語言是很有趣的，在過去二十年裡，析取語言被大量的研究。而析取語言和析取序對，彼此之間具有強烈的聯繫，有好好研究它的價值。

在本篇論文中，我們將定義出新的析取序對，並對它做研究，和得出一些新的性質。令Q^(1)=Q和{1}的聯集，Q^(i)={f^i|f屬於Q} 對任意的i大於等於2。某些語言A和Q^(i)的交集會是析取語言，是已經被證明過的。

The most important and practical languages in the field of computer science are context-free languages, and regular language is a particular kind of context-free languages. On the opposite side of regular language is the disjunctive language. Both disjunctive language and disjunctive pair were first defined by Shyr in 1977.

The properties of disjunctive language are interest and have been studied intensively in the past two decades. The classes of disjunctive pair and disjunctive language are strongly connected and worth to study.

In this work, the new kinds of disjunctive pair are studied and obtained several of their characterizations. Let Q^(1)=Q∪{1};Q^(i)={f^i|f ∈Q} for any i ≥ 2. Some languages A such that A ∩ Q^(i), i ≥ 1 are disjunctive have
been found.

Contents
摘要 I
Abstract II
謝誌 III
Contents IV
1 Introduction 1
2 Disjunctive Languages 7
3 Languages Related To The Overlapping Order 10
4 Other Disjunctive Languages 15
5 Disjunctive Pairs 25
Reference 27

[1] Chu, Danny D. and Town Hsiang-Sheng, Another Proof on a Theorem of
Lyndon and Sch¨utzenberger in a Free Monoid, Scoochow Journal of mathematics,
4 (1978), 143-146.

[2] Hsu, S.C., Ito, M. and Shyr, H.J., Some Properties of Overlapping Order
and Related Languages, Scoochow Journal of mathematics, 15, June (1989),
29-45.

[3] Lyndon, R.C. and Sch¨utzenberger, M.P., The Equation a^M = b^Nc^P in a Free
Group, Michigan Math. J. 9 (1962), 289-298.

[4] Lin, Kuang-Nan, On Some Classes of Languages and Codes, Ph.D. Thesis,
Tamkang College of Arts and Sciences (1979).

[5] Reis, C.M. and Shyr, H.J., Some Properties of Disjunctive Languages on a
Free Monoid, Information and Control, 37, No.3, June (1978), 334-344.

[6] Shyr, H.J., Disjunctive Languages on a Free Monoid, Information and Control,34 (1977), 123-129.

[7] Shyr, H.J. and Thierrin, G., Disjunctive Language and Codes, Fundamentals
of Computation Theory, Proceedings of the 1977 Inter. FCT-Conference,
Poznan, Poland, Lecture Notes in computer Science NO. 56 Springer-Verlag
(1977), 171-176.

[8] Shyr, H.J. and Tsai, C.S., A Note on Languages which are Dense Subsemigroups,
Scoochow Journal of mathematics, 11 June (1985), 117-122.