Signoĉeno

El Vikipedio, la libera enciklopedio

Signoĉenosignovico estas vico da signoj.

Matematika teorio[redakti | redakti fonton]

Alfabeto Σ estu nemalplena aro, kies elementoj kutime nomiĝas signojliteroj. Signoĉenovorto 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[redakti | redakti fonton]

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[redakti | redakti fonton]

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[redakti | redakti fonton]

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