So che tutti i linguaggi finiti sono anche regolari. Ma perchè esattamente è cosi?
Inizia con la definizione di linguaggio regolare: questa e' una definizione, non c'e' un perche'. E' cosi' e basta.
Un linguaggio finito e' un linguaggio che ha un numero finito di stringhe, ed e' ovviamente regolare, visto che:
1) la stringa di lunghezza zero fa parte del linguaggio
2) i singoli simboli dell'alfabeto fanno parte del linguaggio
3) la concatenazione dei singoli simboli fa parte del linguaggio.
4) essendo finito, non conterra' tutte le possibili combinazioni di concatenazion di simboli, ma questo non centra.
E' ovvio che qualunque sottoinsieme di un linguggio regolare e' anch'esso regolare, visto che tutte le sue stringhe possono essere create a partire dall'alfabeto ed utilizzando le regole della definizione.
Certo, si possono creare anche stringhe che non fanno parte del linguaggio finito, ma chissenefrega!
Come posso definire in modo formale le espressioni regolari andando per casi?
Non sono casi, ma regole.
Mettiamola cosi:
1) un insieme finito lo puoi definire enumerando si singoli elementi (anche se sono 10^100, ci vuole un po' di carta (e non basterebbero tutti gli atomi dell'universo che sono circa 10^60), ma si puo' fare)
2) e' ovvio che non puoi fare lo stesso per un insieme infinito. Per un insieme infinito devi usare delle regole per decidere se un elemento appartiene all'insieme.
Ad esempio:
alfabeto -> {a,b}
linguaggio -> { stutte le stringhe fatte nel seguente modo: ab* }
Quanti elementi ha questo linguaggio? Infiniti
"ab" appartiene al linguaggio? Certo
Una "a" seguita da 10^1.000.000 di "b" appartiene al linguaggio? Certo
"aab" appartiene al linguaggio? Si? No? Forse?
Come posso definire un linguaggio a partire dalla sua grammatica?
E' la grammatica che definisce il linguaggio, non viceversa. La grammatica E' il linguaggio. La grammatica indica le regole che permettono di decidere se una stringa qualunque appartiene al linguaggio. Il linguaggio e' l'insieme di tutte le stringhe che pososno essere create a partire dalla grammatica, quindi ha dimensione infinita.
La grammatica ha due compiti:
1) partendo dalla stringa vuota e dall'alfabeto, fornire delle regole per generare tutte le stringhe del linguaggio. Sono infinite!!! Ma si possono creare una alla vola iniziando dalla stringa vuota
2) decidere se una stringa qualunque appartiene al linguaggio
2.1) ovviamente la stringa deve essere composta da simpoli appartenenti all'alfabeto altrimenti e' ovvio che non puo' appartenere al linguaggio
2.2) poi bisogna trovare una sequenza di regole da applicare alla stringa vuota per generare la stringa fornita come riferimento. Se questa sequenza di regole esiste, allora la stringa appartiene al linguaggio, altrimenti no.
Ed e' quello che fa un compilatore: la stringa in ingresso e' il codice sorgente, e il processo di compilazione consiste nel trovare la sequenza di regole che servono per generare esattamente il codice sorgente. E se questa ricerca fallisce, viene generato il mitico "syntax error"
Dato un linguaggio regolare c'è una sola espressione regolare che lo denota? o ce ne sono tan
Ce ne sono infinite, ma esistono anche i teoremi che permettono di dimostrarne l'equivalenza.
Ad esempio esiste il teorema che permette di dimostrare l'equivalenza di un automa a stati NON deterministico, con uno deterministico.
Esempio:
L1 = { ab* }
L2 = { a, ab, ab+ }
L1 ed L2 sono equivalenti. Qui la corrispondenza e' ovvia. Ma se il linguaggio e' formato da tante regole, e da un alfabeto ampio, la cosa non e' per nulla scontata.
A partire dal un linguaggio regolare come posso costruire la grammatica lineare destra che lo genera?
Bisogna rimaneggiare un po' le regole .