Stringhe, alfabeto e linguaggio

Esempio

Ad esempio, la parola x="string" è una stringa formata dai simboli delle lettere inglesi "s", "t", "r", "i", "n", "g" costruita utilizzando l'alfabeto inglese di 26 lettere.

E' una stringa composta da 6 simboli.

$$ |x| = |"string"|= 6 $$

L'espressione aritmetica "1+2-3" è, invece, una stringa costituita dai simboli "1", "2", "3", "+", e "-". In questo caso è una stringa composta da 5 simboli.

$$ |x| = |"1+2-3"|= 5 $$

Una stringa di lunghezza zero $ x = "" $ è detta stringa vuota e spesso viene indicata con il simbolo ε.

$$ x = "" = \epsilon $$

La stringa vuota si può vedere come lo zero dell'addizione perché non modifica la lunghezza di una stringa quando viene aggiunta.

Ad esempio se la stringa è x="cane", la concatenazione con la stringa vuota non modifica il suo contenuto.

$$ x + \epsilon = "cane" + "" = "cane" $$

La concatenazione è l'aggiunta di una stringa al termine di un altra stringa. Ad esempio se una stringa è x="abc" e un'altra stringa è y="def" allora la loro concatenazione è "abcdef"

$$ x + y = "abc" + "def" = "abcdef" $$

A volta per indicare la concatenazione si usa anche la notazione moltiplicativa perché si omette il simbolo ed è più sintetica.

$$ xy = "abcdef" $$

Una stringa x è un prefisso di un'altra stringa w se su può aggiungere qualcosa a x (cioè, concatenare una stringa y) per ottenere w. Ad esempio, se w="abcdef", x="abc" e y="def", allora x="abc" è un prefisso di w="acbdef" perché xy="abcdef" = w.

$$ w = xy = "abcdef" $$

Si dice che x è un prefisso proprio di w se x è un prefisso di w ma x stesso non è uguale a w. Quindi, "abc" è un prefisso proprio di "abcdef", ma "abcdef" non è un prefisso proprio di "abcdef".

L'inverso di un stringa x si indica con il simbolo R in apice $ x^R $

$$ x = "cane" $$

$$ x^R = "enac" $$

Una sottostringa è una sequenza di simboli o caratteri consecutivi (stringa) contenuta dentro un'altra stringa. Ad esempio, nella stringa "programmazione"

$$ x="programmazione" $$

alcune delle sue sottostringhe sono "pro", "gramma", "zione" e "azione".

$$ w_1 = "pro" $$

$$ w_2 = "gramma" $$

$$ w_3 = "zione" $$

In generale, qualsiasi sequenza di caratteri consecutivi che si trovano all'interno di una stringa più lunga può essere considerata una sottostringa di quella stringa.

La potenza di una stringa \( x^n \) rappresenta la concatenazione della stringa \( x \) con se stessa per \( n \) volte. Ad esempio, se la stringa \( x \) è "abc" e \( n \) è 3, allora \( x^n \) sarà "abcabcabc".

$$ x= "abc" $$

$$ x^3 = "abcabcabc" $$

In termini formali:

• \( x^0 \) è la stringa vuota.
• \( x^1 \) è la stringa \( x \) stessa.
• \( x^n \) per \( n > 1 \) è la concatenazione di \( x \) con \( x^{n-1} \).

Ecco un esempio pratico. Se \( x = "hello" \) e \( n = 3 \), allora \( x^3 = "hellohellohello" \).

$$ x^0 = \epsilon $$

$$ x^1 = "hello" $$

$$ x^2 = xx = "hellohello" $$

$$ x^3 = xxx = "hellohellohello" $$

Un esempio semplice di linguaggio formale con l'alfabeto \(\Sigma = \{a, b, c\}\) potrebbe essere definito come il linguaggio di tutte le stringhe che iniziano con "a" e terminano con "c", con qualsiasi combinazione di lettere dell'alfabeto (inclusa nessuna) tra di esse. Questo linguaggio può essere espresso come segue:

$$  L = \{a(bc)^*c\} $$

Dove:

• $ a $ e $ c $ sono simboli fissi che devono apparire rispettivamente all'inizio e alla fine di ogni stringa del linguaggio.
• $ (bc)^* $ indica che la sequenza "bc" può ripetersi zero o più volte.

Esempi di stringhe nel linguaggio:

- "ac" (la sequenza "bc" non appare, ed è accettabile perché il simbolo "*" indica zero o più ripetizioni)
- "abcc" (la sequenza "bc" appare una volta)
- "abcbcc" (la sequenza "bc" appare due volte)
- "abcbcbcc" (la sequenza "bc" appare tre volte)

Queste stringhe rispettano la regola di iniziare con "a" e terminare con "c", con la possibilità di avere la sequenza "bc" ripetuta qualsiasi numero di volte (incluso zero) tra di esse.

Esempi di stringhe fuori dal linguaggio:

Queste stringhe non fanno parte del linguaggio definito perché non iniziano con "a" e terminano con "c" con la sequenza "bc" ripetuta zero o più volte in mezzo.

- "a"
- "abc"
- "bac"
- "cbc"
- "accb"

Questo esempio mostra come si possano definire linguaggi formali con regole precise riguardanti la struttura delle stringhe, basandosi su un alfabeto specifico.

Nell'insieme delle stringhe che caratterizza un linguaggio si usa comunemente lo stesso ordine lessicografico dei dizionari.

Ad esempio, "apple" viene prima di "banana" perché 'a' viene prima di 'b' nell'alfabeto.

In alcuni casi si utilizza l'ordine shortlex che è una variazione dell'ordine lessicografico dove le stringhe più corte precedono quelle più lunghe.

Ad esempio, nell'ordine lessicografico shortlex modificato per l'alfabeto {0,1}, la sequenza delle stringhe sarà: stringa vuota (ε), "0", "1", "00", "01", "10", "11", "000", e così via. Quindi, le stringhe sono ordinate prima per lunghezza e poi per ordine lessicografico

Un linguaggio è detto prefisso-libero se nessuna stringa nell'insieme è un prefisso proprio di un'altra stringa nell'insieme.

Questo significa che non ci sono due stringhe tali che una sia l'inizio (prefisso) dell'altra.

Ad esempio, nell'insieme {"100", "101", "11"}, nessuna stringa è un prefisso proprio di un'altra, quindi è prefisso-libero.

Viceversa, l'insieme {"10", "101", "11"} non è prefisso-libero perché "10" è un prefisso proprio di "101".

Esempio. Basandoci sull'esempio precedente, possiamo definire una classe di linguaggio che include variazioni del linguaggio basato sull'alfabeto \(\Sigma = \{a, b, c\}\). La classe può essere definita come insieme di linguaggi \(L_n\) dove ogni linguaggio è costituito da stringhe che iniziano con "a", terminano con "c", e contengono una sequenza specifica ripetuta \(n\) volte, dove \(n\) è un numero naturale (incluso lo 0).

Esempi di linguaggi nella classe:

Ecco alcuni linguaggi possibili:

• \(L_0\) potrebbe essere il linguaggio che contiene solo la stringa "ac", senza alcuna ripetizione tra "a" e "c". Quindi, L₀ contiene solo la stringa "ac". Non contiene altre stringhe.
• \(L_1\) potrebbe essere il linguaggio delle stringhe che iniziano con "a", seguono con una sequenza "b" o "c", e terminano con "c". Ad esempio, L1 può contenere stringhe come "abc", "acc".
• \(L_2\) potrebbe includere stringhe che iniziano con "a", seguono due combinazioni possibili di "b" e di "c" in mezzo, e terminano con "c". Ad esempio, L₂ può contenere stringhe come "abbc", "abcc", "acbc", "accc".

Questa classe di linguaggio mostra come possiamo costruire una varietà di linguaggi formali partendo da un principio comune, ma variando un aspetto specifico.