Käytössäni on n-kirjaiminen aakkosto. Lähden sijoittamaan näitä kirjaimia peräkkäin siten, ettei mikään m-kirjaimen mittainen osasana esiinny kirjainjonossani missään kohdassa uudelleen. Kuinka pitkän kirjainjonon ('teoksen') voin näin kirjoitaa?
Esimerkiksi voisimme olettaa, että n=26 (englanninkielinen aakkosto) ja m=5 (viiden kirjaimen mittaiset osasanat).
Esimerkiksi voisimme olettaa, että n=26 (englanninkielinen aakkosto) ja m=5 (viiden kirjaimen mittaiset osasanat).
Vastaukset 3
Vanhimmat
Onko tosi, ettei täältä löydy ketään tietotekniikan kannalta hyvin keskeisen matematiikan osa-alueen, ns. 'formaalisten kielten' asiantuntijaa, joka osaisi vastata tähän kysymykseen?
Myös verkkoteorian asiantuntijoilla voisi olla sanansa sanottavana tähän kysymykseen.
Mitä...helvettiä...sä...oikein...puhut...?
Pitäiskö sun hankkia joku oikea harrastus tai tavallinen ystävä?
Aakkosto
ß on ƒaƒarellinen ei-tyhjƒa joukko symboleja, joita sanomme
kirjaimiksi
.
Aakkoston ß
sana
on sen ƒaƒarellinen kirjainjono.
Tyhjƒaƒa sanaa merkitsemme
∏
.
Aakkoston ß kaikkien sanojen joukkoa merkitsemme ß
§
. Tƒatƒa joukkoa sanomme
aakkoston ß generoimaksi
vapaaksi monoidiksi
.
Joukko ß
= ß
§
nf
∏
g
on aakkoston ß generoima
vapaa puoliryhmƒa
.
Vapaan monoidin ß
§
mielivaltainen osajoukko
L
on aakkoston ß
kieli
.
Olkoon
w
2
ß
§
,
w
=
x
1
x
2
:::x
m
, missƒa
x
1
;:::;x
m
2
ß. Sanan
w
pituus
(merk.
j
w
j
) on sanassa
w
esiintyvien kirjainten lukumƒaƒarƒa ts.
j
w
j
=
m
.
Joukko ß on isomorØnen joukon ß
§
kaikkien 1-pituisten sanojen joukon kanssa.
Yleensƒa nƒamƒa joukot samaistetaan ja siten ß
μ
ß
μ
ß
§
.
Sanan
w
=
x
1
x
2
:::x
m
2
ß
§
peilikuva
on sana
x
m
:::x
2
x
1
.
Sana
u
2
ß
§
on sanan
w
2
ß
§
osasana
, jos on olemassa sanat
p;s
2
ß
§
, joilla
w
=
pus
. Sanan
w
kaikkien osasanojen joukkoa merkitsemme
SW
(
w
).
Jos
p
=
∏
, sana
u
on sanan
w
alkuosa
l.
preØksi
. Jos
s
=
∏
, sana
u
on sanan
w
loppuosa
l.
su±ksi
.
Sanan
w
2
ß
§
kaikkien alkuosien joukkoa merkitsemme
PREF
(
w
) ja kaikkien
loppuosien joukkoa
SUFF
(
w
).
Tietyn kirjaimen
x
2
ß esiintymien lukumƒaƒarƒaƒa sanassa
w
2
ß
§
merkitsemme
]
x
(
w
).
Formaalisti voimme mƒaƒaritellƒa funktion
]
x
: ß
§
!
IN
asettamalla:
1) jokaisella
y
2
ß on
]
x
(
y
) = 1, kun
y
=
x
ja
]
x
(
y
) = 0 muulloin ja
2) kaikilla
y
2
ß ja
w
2
ß
§
on
]
x
(
yw
) =
]
x
(
y
)
]
x
(
w
).
Helposti todetaan, ettƒa
]
x
(
∏
) = 0 ja
]
x
(
uv
) =
]
x
(
u
)
]
x
(
v
) kaikilla
x
2
ß ja
u;v
2
ß
§
.