Signoĉeno

El Vikipedio, la libera enciklopedio
Jump to navigation Jump to search

Signoĉeno estas finia vico da signoj.

Matematika teorio[redakti | redakti fonton]

Estu finia nemalplena aro Σ da signoj, en la teorie kutime nomata alfabeto. Ĉeno — aŭ, matematike, vorto — super Σ estas ajna finia vico da signoj el Σ. Ekz-e se Σ = {q, ♪}, tiam q♪q♪♪ estas ĉeno super Σ.

La longo de ĉ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 ĉeno super Σ kies longo estas 0; en la teorio oni kutime signas ĝin per ε: |ε| = 0 (aŭ λ, kio koheras kun Λ simbolanta la malplenan aron).

La aron da ĉiuj ĉ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 ĉenoj super Σ, simbole Σ*, oni difinas kiel

Kroĉo kaj subĉenoj[redakti | redakti fonton]

Kroĉo estas grava duloka operacio super Σ*. Por ĉenoj s kaj t el Σ* ilia kroĉ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.