Linguaggio formale

Definizione di linguaggio formale

In Informatica teorica,un linguaggio formale è un insieme di stringhe costruite su di un alfabeto.

Formalmente, un linguaggio formale è definito come un sottoinsieme di (l’universo) che rappresenta l’insieme di tutte le sequenze finite (stringhe) che si possono formare con i simboli di un alfabeto , che è un insieme finito e non vuoto di simboli (o caratteri), ad esempio .

1. Potenze dell’alfabeto ():
   • (l’insieme contenente solo la stringa vuota, indicata con o talvolta ).
   • (l’insieme di tutte le stringhe di lunghezza 1).
   • (l’insieme di tutte le stringhe di lunghezza 2).
   • è l’insieme di tutte le stringhe di lunghezza .
2. Chiusura di Kleene: l’insieme è definito come l’unione di tutte le possibili potenze dell’alfabeto, da zero a infinito:

Esempio pratico di linguaggio formale

Consideriamo un alfabeto binario .

Applicando la chiusura di Kleene:

• … e così via.

Quindi, per l’alfabeto binario è l’insieme infinito che contiene tutte le possibili stringhe binarie: