School of Computer Science and Engineering, University of Electronic Science & Technology of China, Chengdu, Sichuan, China

---

Abstract—This paper focuses on the basic operations of Chomsky’s languages. The validity and the effectiveness of some closure operations, such as union operator, product operator and Kleene Closure operator, are discussed in detail. The crosstalk problems in Context-Sensitive Languages (CSL) and Phrase Structure Languages (PSL) are analyzed, and a valuable method to solve this problem is presented by suing the alphabet of the operating languages. In addition, according to the valid closure property of regular languages (RL), a simple method to create a regular expression (RE) is proposed. The closure property of the permutation operator in Context-Free Languages (CFL) is proved and tested. In conclusion, by using our proposed methods, the exact type of a given language can be proved theoretically. By the way, the grammar to produce complex language can be created easy. Finally ,the constructing ε -NFA with the closure property is proved.

Index Terms—language operation, valid closure property, crosstalk, context-free permutation

[PDF]

Cite: Wenyu Chen, Xiaobin Wang, Xiaoou Cheng, and Shixin Sun, " Analysis of Valid Closure Property of Formal Language," Journal of Computers vol. 5, no. 2, pp. 322-329, 2010.