Signoĉeno

Signoĉeno aŭ signovico estas vico da signoj.

 Matematika teorio 
Alfabeto Σ estu nemalplena aro, kies elementoj kutime nomiĝas signoj aŭ literoj. Signoĉeno aŭ vorto super alfabeto Σ estas ajna finia vico da signoj el Σ. Ekz-e se Σ = {q, ♪}, tiam q♪q♪♪ estas signoĉeno super Σ.

La longo de signoĉeno ĉ estas la nombro de signoj en ĉ (t.e. la longo de la vico), ĝi estas nenegativa entjero, ofte signata kiel |ĉ|. La malplena signoĉeno estas la unika signoĉeno kies longo estas 0; oni kutime signas ĝin per ε: |ε| = 0 (aŭ λ, kio koheras kun Λ simbolanta la malplenan aron).

La aron da ĉiuj signoĉenoj super Σ, kies longo egalas al n, oni signas per Σⁿ. Ekz-e por Σ = {0, 1} la aro Σ² = {00, 01, 10, 11}. Interalie, Σ0 = {ε} por ĉiu ajn Σ.

La aron da ĉiuj signoĉenoj super Σ, simbole Σ*, oni difinas kiel


 Kunkroĉo kaj subĉenoj 
Kunkroĉo estas grava duloka operacio super Σ*.
Por signoĉenoj s kaj t el Σ* ilia kunkroĉo estas la vico da signoj s sekvata de la vico da signoj t, simbole st. Ekz-e, se Σ = {a, b, c, ĉ, ..., z}, s = signo kaj t = ĉeno, tiam st = signoĉeno kaj ts = ĉenosigno.

Signoĉeno s estas subĉeno de t se ekzistas tiaj (eventuale malplenaj) signoĉenoj u kaj v, ke t = usv.

 Leksikografia ordo 
En diversaj situacioj oni bezonas difini ordon super la signoĉenoj. Se la «alfabeto» Σ havas tutecan ordon, tiam eblas uzi ĝin por difini tutecan leksikografian ordon super Σ*.

 Signoĉenoj en komputado 
Signoĉenoj estas grava koncepto en programlingvoj, kie ili disponeblas kiel simpla aŭ difinebla malsimpla datumtipo.

Kategorio:Formalaj lingvoj
Kategorio:Datumtipoj