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})\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Describing Regular Closure of Linear Languages by Semi Conditional Insertion Deletion Systems

  • Indhumathi Raman

摘要

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})\) .