Premetto che è un post un pò a cazzo che dovrò sistemare comunque per chi si avvicina all'informatica può essere utile
..
1) ALFABETO è un insieme finito di simboli sigma (con sigma indico il nostro alfabeto)
2) DEFINIAMO LE STRINGHE su un alfabeto sigma: sequenze finite di simboli di sigma.
Sulle stringhe possiamo prendere prefissi, suffissi, sottostringhe.
-Stringa vuota, ce n'è solo una per alfabeto, si indica con epsilon o landa.
-Suffisi abcc, in questo caso i suffissi sono le combinazioni: bcc, cc o c.
- Postfissi abcc i post fissi in questo caso sono: abcc , abc, ab, a.
-sottostringhe abccabc, il pezzo "bccab" è una sottostringa. es. se prendessimo tutta la stringa abccabc questo viene indicato con sottostringa banale.
-opreazione di cocatenazione S1xS2: abcxccb= abcccb, la cocatenazione non è commutativa.
Un Linguaggio su Sigma è un insieme di stringhe su Sigma.
0 = [] linguaggio vuoto
[abb, b, Stringa vuota] 3 stringhe, linguaggio finito.
A= [x/ prop.] es. di espressioni sugli insiemi.
L0 = [ab
n / n>o] --> [ ab, abb, abbb, ecc] = Linguaggio infinito.
Esempio Linguaggio:
L1 = [ ba
n b
m / n >= 0, m > 1] Stringa più corta = [ bbb, babb]
Operazioni fra linguaggiU - Unione
x - Concatenazione (potenze)
L* - Stella di Kleene
Edited by G.E.K.O - 15/10/2012, 23:45
