请输入您要查询的字词:

 

单词 InsertionOperationOnLanguages
释义

insertion operation on languages


Let Σ be an alphabet, and u,v words over Σ. An insertion of u into v is a word of the form v1uv2, where v=v1v2. The concatenationMathworldPlanetmath of two words is just a special case of insertion. Also, if w is an insertion of u into v, then v is a deletion of u from w.

The insertion of u into v is the set of all insertions of v into u, and is denoted by vu.

The notion of insertion can be extended to languagesPlanetmathPlanetmath. Let L1,L2 be two languages over Σ. The insertion of L1 into L2, denoted by L1L2, is the set of all insertions of words in L1 into words in L2. In other words,

L1L2={uvuL1,vL2}.

So uv={u}{v}.

A language L is said to be insertion closed if LLL. Clearly Σ* is insertion closed, and arbitrary intersectionMathworldPlanetmath of insertion closed languages is insertion closed. Given a language L, the insertion closure of L, denoted by Ins(L), is the smallest insertion closed language containing L. It is clear that Ins(L) exists and is unique.

More to come…

The conceptMathworldPlanetmath of insertion can be generalized. Instead of the insertion of u into v taking place in one location in v, the insertion can take place in several locations, provided that u must also be broken up into pieces so that each individual piece goes into each inserting location. More precisely, given a positive integer k, a k-insertion of u into v is a word of the form

v1u1vkukvk+1

where u=u1uk and v=v1vk+1. So an insertion is just a 1-insertion. The k-insertion of u into v is the set of all k-insertions of u into v, and is denoted by u[k]v. Clearly [1]=.

Example. Let Σ={a,b}, and u=aba, v=bab, and w=bababa. Then

  • w is an insertion of u into v, as well as an insertion of v into u, for w=vuλ=λvu.

  • w is also a 2-insertion of u into v:

    • the decompositions u=(ab)(a) and v=(b)(ab)λ

    • or the decompositions u=λu and v=λvλ

    produce (b)(ab)(ab)(a)λ=λλvuλ=w.

  • Finally, w is also a 2-insertion of v into u, as the decompositions u=λuλ and v=vλ produce λvuλλ=w.

  • uv={ababab,babaab,baabab,bababa}.

From this example, we observe that a k-insertion is a (k+1)-insertion, and every k-insertion of u into v is a (k+1)-insertion of v into u. As a result,

u[k]v(u[k+1]v)(v[k+1]u).

As before, given languages L1 and L2, the k-insertion of L1 into L2, denoted by L1[k]L2, is the union of all u[k]v, where uL1 and vL2.

Remark. Some closure properties regarding insertions: let be the family of regular languages, and the family of context-free languages. Then is closed under [k], for each positive integer k. is closed [k] only when k=1. If L1 and L2, then L1[k]L2 and L2[k]L1 are both in . The proofs of these closure properties can be found in the reference.

References

  • 1 M. Ito, Algebraic Theory of Automata and Languages, World Scientific, Singapore (2004).

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/7/10 18:33:57