Word (teoretisk informatikk)

I teoretisk informatikk er et ord en endelig sekvens av symboler i et alfabet . I motsetning til den naturlige språkbetydningen av ord , som alltid har en uavhengig betydning, har et ord i teoretisk informatikk ingen språklig betydning. Det er bare et nytt begrep for en streng .

Ord eller ord er elementene i et formelt språk . De er derfor viktige for matematisk modellering , for teorien om programmeringsspråk , for beregbarhetsteori og andre områder av teoretisk informatikk.

definisjon

Det skal være et gitt alfabet og et naturlig tall fra settet med naturlige tall, inkludert null ( ). Et ord av lengde er en endelig sekvens med for alle . ${\ displaystyle \ Sigma}$${\ displaystyle n}$${\ displaystyle \ mathbb {N} _ {0}}$${\ displaystyle \ mathbb {N} _ {0} = \ {0,1,2, \ ldots \}}$${\ displaystyle w}$${\ displaystyle n}$${\ displaystyle (x_ {1}, x_ {2}, x_ {3}, \ ldots, x_ {n})}$${\ displaystyle x_ {i} \ in \ Sigma}$${\ displaystyle i \ in \ {1, \ ldots, n \}}$

Lengden på et ord er angitt som; antall ganger tegnet vises i ordet med . Et spesialord er det tomme ordet , som ikke består av noe symbol (har lengden 0) og vanligvis er representert med den greske bokstaven ( epsilon ) (som også finnes av og til). Settet med alle ord som kan dannes fra et alfabet er kløveraske og positivt omslag over dette alfabetet. Dette er den usammenhengende unionen ${\ displaystyle n}$${\ displaystyle w}$${\ displaystyle | w |}$${\ displaystyle x}$${\ displaystyle w}$${\ displaystyle | w | _ {x}}$${\ displaystyle \ varepsilon}$${\ displaystyle \ Lambda}$${\ displaystyle \ Sigma}$

${\ displaystyle \ Sigma ^ {*}: = \ bigcup _ {n \ in \ mathbb {N} \ cup \ {0 \}} \ Sigma ^ {n}}$.

De ikke-tomme ordene er deretter følgelig den 'positive konvolutten'

${\ displaystyle \ Sigma ^ {+}: = \ Sigma ^ {*} \ setminus \ {\ varepsilon \} = \ bigcup _ {n \ in \ mathbb {N}} \ Sigma ^ {n}}$.

Den forenklede notasjonen brukes ofte til å indikere et ord , men dette er bare mulig hvis alfabetet som brukes, tillater at symbolene som brukes, blir tildelt tydelig. Denne korte stavemåten kan ikke brukes med alfabetet , for eksempel fordi stavemåten ikke tydelig angir om ordet , eller er ment. ${\ displaystyle w = x_ {1} x_ {2} x_ {3} \ ldots x_ {n}}$${\ displaystyle \ Sigma = \ {a, aa \}}$${\ displaystyle w = aaa}$${\ displaystyle (a, aa)}$${\ displaystyle (aa, a)}$${\ displaystyle (a, a, a)}$

Ord med lengde kan forstås slik:${\ displaystyle n}$

• som endelige sekvenser (sekvens) - siden tupler kan forstås som sekvenser med endelig lengde${\ displaystyle n}$
• som elementer i det foldede kartesiske produktet - siden tupler også kan forstås på den måten${\ displaystyle n}$

Eksempler

La det være alfabetet med latinske bokstaver og . Da er ordene og eksemplene på ord over og et ord er over . Du kan se det og er. ${\ displaystyle \ Sigma _ {1}}$${\ displaystyle \ Sigma _ {2} = \ lbrace \ diamondsuit, \ heartsuit, \ spadesuit, \ clubsuit \ rbrace}$${\ displaystyle w_ {1} = hus}$${\ displaystyle w_ {2} = xyzzy}$${\ displaystyle \ Sigma _ {1}}$${\ displaystyle w_ {3} = \ heartsuit \ clubsuit \ clubsuit \ heartsuit \ spadesuit}$${\ displaystyle \ Sigma _ {2}}$${\ displaystyle | w_ {1} | = 4}$${\ displaystyle | w_ {2} | = | w_ {3} | = 5}$

Operasjoner på ord

Sammenkobling

Den sammenkobling eller kjeden er en kombinasjon av to ord for å danne et nytt ord som er opprettet ved å forbinde de to symbolsekvensene. Sammenkoblingen av de to ordene og over et alfabet er indikert med eller og er definert av: ${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle \ Sigma}$${\ displaystyle xy}$${\ displaystyle x \ circ y}$

${\ displaystyle xy = x \ circ y: = (x_ {1}, x_ {2}, x_ {3}, \ ldots, x_ {n}, y_ {1}, y_ {2}, y_ {3}, \ ldots, y_ {k})}$

I henhold til definisjonen av ordet og med og for alle og . I følge definisjonen ovenfor er det et prefiks og et suffiks av ordet opprettet av sammenkoblingen . Lengden på et sammenkoblet ord tilsvarer summen av lengden på de enkelte (delvise) ordene. Så for hvert ord og : ${\ displaystyle x = (x_ {1}, x_ {2}, x_ {3}, \ ldots, x_ {n})}$${\ displaystyle y = (y_ {1}, y_ {2}, y_ {3}, \ ldots, y_ {k})}$${\ displaystyle n, k \ in \ mathbb {N} _ {0}}$${\ displaystyle x_ {i}, y_ {j} \ in \ Sigma}$${\ displaystyle i \ in \ {1, \ ldots, n \}}$${\ displaystyle j \ in \ {1, \ ldots, k \}}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle x \ circ y}$${\ displaystyle u}$${\ displaystyle v}$

${\ displaystyle | u \ circ v | = | u | + | v |}$,

og for den absolutte hyppigheten av et tegn : ${\ displaystyle x}$

${\ displaystyle | u \ circ v | _ {x} = | u | _ {x} + | v | _ {x}}$.

Det nøytrale elementet i sammenkoblingen er det tomme ordet, siden det for ethvert ord gjelder at: ${\ displaystyle w}$

${\ displaystyle w \ circ \ varepsilon = \ varepsilon \ circ w = w}$

Siden sammenkoblingen også er assosiativ , utgjør trippelen en monoid fra settet med alle ord over ethvert alfabet , kombinasjonen av sammenkoblingen og det tomme ordet som et nøytralt element . Assosiativitet betyr at parenteser lett kan utelates: ${\ displaystyle (\ Sigma ^ {*}, \ circ, \ varepsilon)}$${\ displaystyle \ Sigma}$

${\ displaystyle (house \ circ \ heartsuit \ clubsuit \ clubsuit \ heartsuit \ spadesuit) \ circ xyzzy = house \ circ (\ heartsuit \ clubsuit \ clubsuit \ heartsuit \ spadesuit \ circ xyzzy) = house \ heartsuit \ clubsuit \ clubsuit \ heartsuit \ spadesuit xyzzy}$

I kontrast er ikke sammenkoblingen kommutativ ; H. ikke for alle ord, og det er sant . For eksempel: ${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle u \ circ v = v \ circ u}$

${\ displaystyle house \ circ \ heartsuit \ clubsuit \ clubsuit \ heartsuit \ spadesuit = house \ heartsuit \ clubsuit \ clubsuit \ heartsuit \ spadesuit \ not = \ heartsuit \ clubsuit \ clubsuit \ heartsuit \ spadesuit house = \ heartsuit \ clubsuit \ clubsuit \ hjertdrakt \ spadesuit \ circ house}$

makt

Den 'te kraft av et ord er definert som fold sammenkjeding av dette ord med seg Definisjonen av strømmen er vanligvis gitt rekursivt.: ${\ displaystyle n}$ ${\ displaystyle w ^ {n}}$${\ displaystyle w}$${\ displaystyle (n-1)}$

${\ displaystyle w ^ {0}: = \ varepsilon}$

${\ displaystyle w ^ {n + 1}: = w ^ {n} \ circ w}$   (for )${\ displaystyle n \ in \ mathbb {N} _ {0}}$

For eksempel:

${\ displaystyle (xyzzy) ^ {0} = \ varepsilon}$

${\ displaystyle (\ heartsuit \ clubsuit \ clubsuit \ heartsuit \ spadesuit) ^ {1} = (\ heartsuit \ clubsuit \ clubsuit \ heartsuit \ spadesuit) ^ {0} \, \ circ \, \ heartsuit \ clubsuit \ clubsuit \ heartsuit \ spadesuit = \ varepsilon \, \ circ \, \ heartsuit \ clubsuit \ clubsuit \ heartsuit \ spadesuit = \ heartsuit \ clubsuit \ clubsuit \ hjørnesuit \ spadesuit}$

${\ displaystyle (house) ^ {3} = (house) ^ {2} \, \ circ \, house = ((house) ^ {1} \, \ circ \, house) \, \ circ \, house = ((\ varepsilon \, \ circ \, house) \, \ circ \, house) \, \ circ \, house = house house house}$

I henhold til definisjonen av sammenkobling er lengden på -th kraften til et ord lik produktet av og lengden på : ${\ displaystyle n}$${\ displaystyle w}$${\ displaystyle n}$${\ displaystyle w}$

${\ displaystyle | w ^ {n} | = n \ cdot | w |}$,

og for den absolutte frekvensen til hvert tegn : ${\ displaystyle x}$

${\ displaystyle | w ^ {n} | _ {x} = n \ cdot | w | _ {x}}$

speilbilde

Den speiling eller omvendt av et ord resultater fra skriftlig bakover. Så hvis det er, så er den endelige sekvensen med og for alle . Så lengden på et ord er lik lengden på refleksjonen: ${\ displaystyle w ^ {R}}$${\ displaystyle w}$${\ displaystyle w}$${\ displaystyle w = (x_ {1}, x_ {2}, x_ {3}, \ ldots, x_ {n})}$${\ displaystyle w ^ {R}}$${\ displaystyle (y_ {1}, y_ {2}, y_ {3}, \ ldots, y_ {k})}$${\ displaystyle k = n}$${\ displaystyle y_ {i} = x_ {n + 1-i}}$${\ displaystyle i \ in \ {1, \ ldots, k \}}$

${\ displaystyle | w ^ {R} | = | w |}$

For eksempel gjelder følgende ord:

${\ displaystyle \ varepsilon ^ {R} = \ varepsilon}$

${\ displaystyle (fig) ^ {R} = bba}$

${\ displaystyle (\ heartsuit \ clubsuit \ spadesuit \ heartsuit) ^ {R} = \ heartsuit \ spadesuit \ clubsuit \ heartsuit}$

Det motsatte av et ord kan også defineres ved hjelp av strukturell induksjon over strukturen til det aktuelle ordet. For dette formålet definerer man det motsatte av det tomme ordet som det tomme ordet i induksjonsbegynnelsen. I induksjonstrinnet er det motsatte av et ord sammensatt av et delvis ord og et symbol definert som sammenkoblingen av symbolet med det motsatte av det delvise ordet:

Induksjonsstart: ${\ displaystyle w = \ varepsilon \ Rightarrow w ^ {R} = \ varepsilon ^ {R}: = \ varepsilon}$

Induksjonstrinn: ${\ displaystyle (w = v \ circ a) \ land (v \ in \ Sigma ^ {*}, a \ in \ Sigma) \ Rightarrow w ^ {R} = (v \ circ a) ^ {R}: = a \ circ (v ^ {R})}$

Slik kan det motsatte av et ord utledes trinnvis:

${\ displaystyle \ varepsilon ^ {R} = \ varepsilon}$

${\ displaystyle (abb) ^ {R} = b \ circ (ab) ^ {R} = b \ circ b \ circ (a) ^ {R} = b \ circ b \ circ a \ circ (\ varepsilon) ^ {R} = b \ circ b \ circ a \ circ \ varepsilon = bba}$

${\ displaystyle (\ heartsuit \ clubsuit \ spadesuit \ heartsuit) ^ {R} = \ heartsuit \ circ (\ heartsuit \ clubsuit \ spadesuit) ^ {R} = \ heartsuit \ circ \ spadesuit \ circ (\ heartsuit \ clubsuit) ^ {R} = \ heartsuit \ circ \ spadesuit \ circ \ clubsuit \ circ (\ heartsuit) ^ {R} = \ heartsuit \ spadesuit \ clubsuit \ heartsuit}$

Et ord som , som er identisk med refleksjonen, kalles et palindrom . Matematisk sett dette speil-symmetriske ord enn de faste refleksjonspunktene ^R sett. ${\ displaystyle abaaba}$

Prefiks, infiks og suffiks

infix

Et infiks er et tillegg i et ord. Hver endelig delsekvens av påfølgende symboler for et ord kalles et infiks eller delvis ord av ordet . Et infiks av et gitt ord er derfor hvert ord som det er (minst) ett for , som gjelder det på den ene siden og på den andre siden for hvert . I følge dette er et ord infiks av et ord hvis og bare hvis det holder at det er minst ett ord og ett ord fra Kleens konvolutt over alfabetet , slik at : ${\ displaystyle w}$${\ displaystyle w}$${\ displaystyle w = (x_ {1}, x_ {2}, x_ {3}, \ ldots, x_ {n})}$${\ displaystyle {\ hat {w}} = (y_ {1}, y_ {2}, y_ {3}, \ ldots, y_ {k})}$${\ displaystyle i \ in \ mathbb {N} _ {0}}$${\ displaystyle k + i \ leq n}$${\ displaystyle x_ {j + i} = y_ {j}}$${\ displaystyle j \ in \ {1, \ ldots, k \}}$${\ displaystyle u}$${\ displaystyle w}$${\ displaystyle p}$${\ displaystyle s}$${\ displaystyle w}$${\ displaystyle p \ circ u \ circ s = w}$

${\ displaystyle u}$ er infiks av ${\ displaystyle w: \; \ Longleftrightarrow \ eksisterer p, s \ i \ Sigma ^ {\ ast}: \; p \ circ u \ circ s = w}$

Hvis ordet med et infiks av ord , og , men ikke ordene , eller det tomme ordet . På mange dataspråk brukes det engelske ordet substring for Infix . ${\ displaystyle {\ hat {w}} = aba}$${\ displaystyle {\ hat {w}} \ in \ lbrace a, b \ rbrace ^ {*}}$${\ displaystyle babaab}$${\ displaystyle abaababb}$${\ displaystyle aba}$${\ displaystyle abba}$${\ displaystyle babbaabbab}$${\ displaystyle \ varepsilon}$

Spesielt er det tomme ordet et infiks av et hvilket som helst ord, og hvert ord er et infix av seg selv. Et infix av et ord som ikke er identisk med dette kalles et reelt infix .

prefiks

Et prefiks er et tillegg til begynnelsen av et ord. Et prefiks av et ord er derfor hvert infiks , som gjelder det og for hvert . Følgelig er prefikset for ordet hvis og bare hvis det er minst en fra Kleens konvolutt over alfabetet det ble generert fra, slik at : ${\ displaystyle w = (x_ {1}, x_ {2}, x_ {3}, \ ldots, x_ {n})}$${\ displaystyle {\ hat {w}} = (y_ {1}, y_ {2}, y_ {3}, \ ldots, y_ {k})}$${\ displaystyle k \ leq n}$${\ displaystyle x_ {j} = y_ {j}}$${\ displaystyle j \ in \ {1, \ ldots, k \}}$${\ displaystyle u}$${\ displaystyle w}$${\ displaystyle s}$${\ displaystyle w}$${\ displaystyle u \ circ s = w}$

${\ displaystyle u}$ er prefiks av ${\ displaystyle w: \; \ Longleftrightarrow \ eksisterer s \ i \ Sigma ^ {\ ast}: \; u \ circ s = w}$

For prefikser er også hvert ord et prefiks for seg selv, og det tomme ordet er et prefiks for ethvert ord. Et prefiks av et ord som ikke er identisk med det kalles et ekte prefiks .

eksempel

Vær , dette er de virkelige prefiksene for : ${\ displaystyle w = abaabb}$${\ displaystyle w}$

• ${\ displaystyle \ varepsilon}$
• ${\ displaystyle a}$
• ${\ displaystyle fra}$
• ${\ displaystyle aba}$
• ${\ displaystyle abaa}$
• ${\ displaystyle abaab}$.

suffiks

Et suffiks , også kalt postfiks, er et tillegg til slutten av et ord. I henhold til definisjonen av infikset er et suffiks av et ord hvert delord som det er ett for , som det er på den ene siden og for hver på den andre . Følgelig er et ord et suffiks av et ord med hvis og bare hvis det er minst ett slikt som er: ${\ displaystyle w = (x_ {1}, x_ {2}, x_ {3}, \ ldots, x_ {n})}$${\ displaystyle {\ hat {w}} = (y_ {1}, y_ {2}, y_ {3}, \ ldots, y_ {k})}$${\ displaystyle i \ in \ mathbb {N} _ {0}}$${\ displaystyle k + i = n}$${\ displaystyle x_ {j + i} = y_ {j}}$${\ displaystyle j \ in \ {1, \ ldots, k \}}$${\ displaystyle u}$${\ displaystyle w}$${\ displaystyle w \ in \ Sigma ^ {\ ast}}$${\ displaystyle p \ in \ Sigma ^ {\ ast}}$${\ displaystyle p \ circ u = w}$

${\ displaystyle u}$ er suffiks av ${\ displaystyle w: \; \ Longleftrightarrow \ eksisterer p \ i \ Sigma ^ {\ ast}: \; p \ circ u = w}$

Som med prefikser og infikser, gjelder det samme for suffikser at det tomme ordet er et suffiks av ethvert ord, og ethvert ord er alltid et suffiks av seg selv. Et suffiks av et ord som ikke er det samme som det kalles et ekte suffiks .

eksempel

Vær , dette er de virkelige suffiksene for : ${\ displaystyle w = abaabb}$${\ displaystyle w}$

• ${\ displaystyle baabb}$
• ${\ displaystyle aabb}$
• ${\ displaystyle fig}$
• ${\ displaystyle bb}$
• ${\ displaystyle b}$
• ${\ displaystyle \ varepsilon}$.

litteratur

• John E. Hopcroft , Jeffry D. Ullman : Introduksjon til automatteori, formelle språk og kompleksitetsteori . 3. korrigert utgave. Addison-Wesley, Bonn et al. 1994, ISBN 3-89319-744-3 ( International Computer Library ). 
• Katrin Erk, Lutz Priese: Teoretisk informatikk. En omfattende introduksjon . 2. utvidet utgave. Springer-Verlag, Berlin et al. 2002, ISBN 3-540-42624-8 , pp. 27-28 ( Springer lærebok ). 
• Gottfried Vossen, Kurt-Ulrich Witt: Grunnkurs i teoretisk informatikk. En applikasjonsorientert introduksjon - for studenter på alle datavitenskapskurs . 4. forbedret og forstørret utgave. Vieweg, Wiesbaden 2006, ISBN 3-8348-0153-4 , s. 15 ( online ). 

Notater og individuelle referanser

1. ↑ Begge flertallsformene er vanlige, jfr. B. dtv-Atlas zur Mathematik , bind I, ISBN 3-423-03007-0 , s. 245 versus Bauer, Goos: Informatik. Bind I, ISBN 3-540-06332-3 , s. 28.
2. ↑ Klaus Reinhardt: Prioriterte betalingsautomater og synkronisering av halvsporsspråk , Fakultet for informatikk ved Universitetet i Stuttgart; PhD-avhandling 1994 (PDF; 509 KB)
3. Is Dette er .${\ displaystyle | w | = \ sum \ limits _ {x \ in \ Sigma} | w | _ {x}}$
4. ↑ Yuri L. Ershov, Eugenii A. Palyutin: Matematisk Logikk . Oversatt fra russisk av Vladimir Shokurov. Revidert fra den russiske utgaven 1979. Mir Publishers, Moskva 1984, s. 16 ( mirtitles.org ). 
5. ^ Definisjon av tuple og dens synonymer: Encyclopedia of Mathematics: Tuple
6. ↑ Refleksjonen av et ord med lengden n er en spesiell selvinvers permutasjon

   ${\ displaystyle \ sigma _ {n} = {\ begin {pmatrix} 1 & 2 & \ cdots & n \\ n & n-1 & \ cdots & 1 \ end {pmatrix}}}$.

   Refleksjonen av vilkårlig lange ord er da foreningen ${\ displaystyle {} ^ {R} = \ bigcup \ {\ sigma _ {n} | n \ in \ mathbb {N} \}}$

weblenker

• Grunnleggende begreper for formelt språk - seksjonen "Word"