HBJ model
In mathematics and computer science, a splicing rule is a transformation on formal languages which formalises the action of gene splicing in molecular biology. A splicing language is a language generated by iterated application of a splicing rule: the splicing languages form a proper subset of the regular languages.
Definition
Let A be an alphabet and L a language, that is, a subset of the free monoid A∗. A splicing rule is a quadruple r = (a,b,c,d) of elements of A∗, and the action of the rule r on L is to produce the language
If R is a set of rules then R(L) is the union of the languages produced by the rules of R. We say that R respects L if R(L) is a subset of L. The R-closure of L is the union of L and all iterates of R on L: clearly it is respected by R. A splicing language is the R-closure of a finite language.[1]
A rule set R is reflexive if (a,b,c,d) in R implies that (a,b,a,b) and (c,d,c,d) are in R. A splicing language is reflexive if it is defined by a reflexive rule set.[2]
Examples
- Let A = {a,b,c}. The rule (caba,a,cab,a) applied to the finite set {cabb,cabab,cabaab} generates the regular language caba∗b.[3]
Properties
- All splicing languages are regular.[4]
- Not all regular languages are splicing.[5] An example is (aa)∗ over {a,b}.[4]
- If L is a regular language on the alphabet A, and z is a letter not in A, then the language { zw : w in L } is a splicing language.[3]
- There is an algorithm to determine whether a given regular language is a reflexive splicing language.[2]
- The set of splicing rules that respect a regular language can be determined from the syntactic monoid of the language.[6]
References
43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.
- 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
My blog: http://www.primaboinca.com/view_profile.php?userid=5889534