Describing Regular Closure of Linear Languages by Semi Conditional Insertion Deletion Systems
摘要
The smallest superclass of linear languages LIN which is closed under the regular operations, namely, Kleene star, union, and concatenation, is called the regular or rational closure of LIN and is denoted by \(\mathbb {L}_{reg}(\textrm{LIN})\) . In this paper, the class \(\mathbb {L}_{reg}(\textrm{LIN})\) is described using insertion-deletion system together with semi conditional regulation. A rule in SCID system is applied whenever all strings in its permitting set are available as substrings and all strings from the forbidden set are absent. We mainly prove that whenever SCID systems simulates the class of linear languages, then with no additional parameters, the SCID system can describe \(\mathbb {L}_{reg}(\textrm{LIN})\) . In particular, SCID systems with degree (2, 1) and sizes (2, 0, 0; 1, 0, 0), (1, 1, 0; 1, 0, 0) and (1, 0, 1; 1, 0, 0) are shown to describe the class of \(\mathbb {L}_{reg}(\textrm{LIN})\) .