Linguaggi regolari

[epdragon]

Qualcuno saprebbe aiutarmi nella dimostrazione? Grazie.
La chiusura di Kleene di un linguaggio regolare è regolare.

[megas_archon]

Non mi sembra ci sia niente da dimostrare, perciò forse devi spiegarti meglio: se \(\Theta\) è un alfabeto, \(\Theta^\star\) è regolare per definizione di come si generano i linguaggi regolari, vedi qui.

[epdragon]

Dovrei spiegare perchè La chiusura di Kleene di un linguaggio regolare è regolare.

[megas_archon]

Il fatto che se $L$ è regolare, \(L^\star\) è regolare è una delle regole ricorsive che definiscono i linguaggi regolari.

Un "linguaggio" su un alfabeto \(\Sigma\) è un sottoinsieme del monoide libero su \(\Sigma\), quindi
\[\text{Lang}(\Sigma) := 2^{\Sigma^\ast}\] Ora dato un linguaggio la stella di Kleene di quel linguaggio è \(\coprod_{k=0}^\infty L^k\), dove \(L^0 := \{\varepsilon\}\) è la parola vuota e \(L^{k+1} := L \ast L^k\) è l'insieme di tutte le tuple ottenute concatenando roba in $L$ con roba in $L^k$.

Ora, un linguaggio regolare su \(\Sigma\) si definisce ricorsivamente mediante delle regole:

1. il linguaggio vuoto è regolare;
2. i singoletti sono tutti linguaggi regolari;
3. l'unione \(A\cup B\) di due linguaggi regolari $A,B$ è regolare;
4. la concatenazione \(A * B\) di due linguaggi regolari \(A,B\) è un linguaggio regolare;
5. la stella di Kleene \(L^\star\) di un linguaggio regolare $L$ è regolare.

In base a 5, se $L$ è regolare \(L^\star\) è regolare per definizione. Da 5+1 discende che \(\{\varepsilon\} = \varnothing^\star\) è regolare.

[epdragon]

Capito. Grazie

[epdragon]

Il fatto che se $L$ è regolare, \(L^\star\) è regolare è una delle regole ricorsive che definiscono i linguaggi regolari.

Un "linguaggio" su un alfabeto \(\Sigma\) è un sottoinsieme del monoide libero su \(\Sigma\), quindi
\[\text{Lang}(\Sigma) := 2^{\Sigma^\ast}\] Ora dato un linguaggio la stella di Kleene di quel linguaggio è \(\coprod_{k=0}^\infty L^k\), dove \(L^0 := \{\varepsilon\}\) è la parola vuota e \(L^{k+1} := L \ast L^k\) è l'insieme di tutte le tuple ottenute concatenando roba in $L$ con roba in $L^k$.

Ora, un linguaggio regolare su \(\Sigma\) si definisce ricorsivamente mediante delle regole:

1. il linguaggio vuoto è regolare;
2. i singoletti sono tutti linguaggi regolari;
3. l'unione \(A\cup B\) di due linguaggi regolari $A,B$ è regolare;
4. la concatenazione \(A * B\) di due linguaggi regolari \(A,B\) è un linguaggio regolare;
5. la stella di Kleene \(L^\star\) di un linguaggio regolare $L$ è regolare.

In base a 5, se $L$ è regolare \(L^\star\) è regolare per definizione. Da 5+1 discende che \(\{\varepsilon\} = \varnothing^\star\) è regolare.

Invece La chiusura di Kleene di un linguaggio regolare è un linguaggio infinito? questa parte non mi è ben chiara

[megas_archon]

Per ogni elemento dell'alfabeto \(a\in\Sigma\), il linguaggio \(\{a\}\) è regolare; allora \(\langle a^n\mid n\ge 0\rangle\) è regolare, e infinito. Quindi...

[epdragon]

Capito! quindi l'affermazione è vera

[epdragon]

Per ogni elemento dell'alfabeto \(a\in\Sigma\), il linguaggio \(\{a\}\) è regolare; allora \(\langle a^n\mid n\ge 0\rangle\) è regolare, e infinito. Quindi...

Invece per quanto riguarda questo: L’intersezione di un linguaggio regolare con un linguaggio non regolare è un linguaggio regolare.

Suppongo sia falsa questa affermazione però non saprei come dimostrarlo formalmente, sapresti aiutarmi? Grazie in anticipo.

[megas_archon]

Capito! quindi l'affermazione è vera

No, non è vera; ma semplicemente perché la chiusura di Kleene del linguaggio vuoto è il singoletto sulla parola vuota. La chiusura di Kleene di un linguaggio regolare e non vuoto è infinita.