Operazioni sui linguaggi formali

Da Wikiversità, l'apprendimento libero.
Jump to navigation Jump to search
lezione
Operazioni sui linguaggi formali
Tipo di risorsa Tipo: lezione
Materia di appartenenza Materia: Linguaggi formali e automi
Avanzamento Avanzamento: lezione completa al 100%.

Operazioni sulle stringhe[modifica]

Concatenazione[modifica]

La concatenzione tra due stringhe, detto anche prodotto tra due stringhe, è definito come:

siano e due stringhe, allora la loro concatenzione è .

La concatenzione è anche indicata con . Gode della proprietà associativa e dell'additività della lunghezza .

Ha come elemento neutro la stringa vuota: .

Sottostringa[modifica]

Diciamo che è sottostringa di se e solo se:

per qualche stringa (detta prefisso) e (detta suffisso).

è sottostringa propria se e solo se e .

Riflessione[modifica]

L'operazione di riflessione è definita come:

sia allora la sua riflessione è .

Gode delle seguenti proprietà:

  • riflessiva:
  • distributiva:
  • valore nullo:

Ripetizione o potenza[modifica]

Si definisce ripetizione o potenza di una stringa la concatenazione di se stessa volte:

con . Se , allora

Esempi:

N.B.: ripetizione e riflessione hanno la precedenza sulla concatenzione! Esempio: e .

Operazioni sui linguaggi[modifica]

Alcune operazioni sui linguaggi sono l'estensione di quelle sulle stringhe.

Riflessione[modifica]

La riflessione di un linguaggio è l'insieme di tutte le stringhe riflesse del linguaggio:

sia un linguaggio, allora

Concatenazione[modifica]

La concatenazione di un linguaggio è definita come il linguaggio contenente la concatenazione delle stringhe dei linguaggi concatenati:

N.B.

Ripetizione o potenza[modifica]

La ripetizione o potenza di un linguaggio viene definita ricorsivamente:

per

N.B.

Esempio:

Come visto la potenza produce un set di stringhe di dimensione fissa e finita . Utilizzando la stringa vuota è possibile ottenere il set di stringhe con lunghezza minore di m.

Esempio:

Operazioni insiemistiche[modifica]

I linguaggi godono delle classiche operazioni insiemistiche:

  • : unione (insieme composto da tutte le stringhe che compongono il primo linguaggio o il secondo linguaggio.)
  • : intersezione (insieme composto da tutte le stringhe che compongono il primo linguaggio e il secondo linguaggio.)
  • : differenza (insieme composto da tutte le stringhe che compongono il primo linguaggio ma non il secondo linguaggio.)
  • : inclusione
  • : inclusione stretta
  • : uguaglianza

Definizioni[modifica]

Definiamo linguaggio universale di un alfabeto come l'insieme di tutte le stringhe di qualsiasi lunghezza sull'alfabeto:

Definiamo complemento di un linguaggio su un alfabeto :

N.B.:

  • .
  • Il complemento di un linguaggio finito è sempre infinito;
  • Il complemento di un linguaggio infinito non è sempre finito.

Chiusura di Kleene[modifica]

La chiusura di Kleene o operatore stella è la chisura riflessiva e transitiva dell'operazione di concatenazione.

Informalmente, questo insieme di stringhe è quello che è possibile generare concatenando due stringhe di L, anche con ripetizioni.

Ad esempio:

è evidentemente sempre infinito, qualsiasi sia il linguaggio . Può capitare che , ad esempio: .

N.B.:

Spesso si utilizza la sintassi per dire che il linguaggio è un linguaggio sull'alfabeto .

Proprietà[modifica]

La chiusura di Kleene gode delle seguenti proprietà:

  • monotonicità:
  • chiusura alla concatenazione:
  • idempotenza:
  • commutatività con riflessione:

Operatore Cross[modifica]

L'operatore cross è la chisura transitiva ma non riflessiva dell'operazione di concatenazione. Sostanzialmente rispetto al precedente l'unione non include la prima potenza

Operatore quoziente[modifica]

L'operatore quoziente, identificato dalla slash (non backslash!). Definito come: .

Esempio: