Linguaggi regolari
Qualcuno saprebbe aiutarmi nella dimostrazione? Grazie.
La chiusura di Kleene di un linguaggio regolare è regolare.
La chiusura di Kleene di un linguaggio regolare è regolare.
Risposte
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.
Dovrei spiegare perchè La chiusura di Kleene di un linguaggio regolare è regolare.
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.
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.
Capito. Grazie
"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.
Invece La chiusura di Kleene di un linguaggio regolare è un linguaggio infinito? questa parte non mi è ben chiara
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...
Capito! quindi l'affermazione è vera
"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...
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.
"epdragon":
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.
"megas_archon":
[quote="epdragon"]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.[/quote]
Per singoletto cosa si intende?
\(\{\bullet\}\)
"megas_archon":
\(\{\bullet\}\)
L’intersezione di un linguaggio regolare con un linguaggio non regolare è un linguaggio regolare. Con questa mi sapresti aiutare?
Ma tu, a cercare di rispondere a queste domande, ci hai provato? Mi sembra che se non ti è chiaro cosa sia un singoletto o quale sia la definizione di regolarità ci sia poco di cui chiedere aiuto.
"megas_archon":
Ma tu, a cercare di rispondere a queste domande, ci hai provato? Mi sembra che se non ti è chiaro cosa sia un singoletto o quale sia la definizione di regolarità ci sia poco di cui chiedere aiuto.
Dal libro non ci ho capito molto per questo chiedevo. Io di solito lo chiamo singleton, ho chiesto per sicurezza...
Quindi, devi trovare un linguaggio non regolare, che intersecato con uno regolare, ne dà uno non regolare. Come si fa?
∑^* ∩∅ va bene questo?
...no?
E il problema non è che hai dato la risposta sbagliata; il problema è che è una risposta data senza pensare [avevo scritto un commento estremamente avvelenato, ma poi i bambini si impressionano].
Un linguaggio non regolare è, ad esempio, dipendente dal contesto o fa delle richieste sulla lunghezza dei suoi elementi; trovane uno: intersecalo con un linguaggio regolare, ad esempio \(\langle a^n\mid n\ge 0\rangle\), cosa viene fuori?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo