Pumping lemma
Innanzitutto buongiorno!
Dimostrare che il seguente linguaggio non è regolare:
$ L=0^n 1 0^n | n >= 1 $
Suppongo che il linguaggio sia regolare.
Quindi prendo una parola $ |w|>m $ con $ m=2n+1 $.
Scompongo $ w $ in $ xyz $ in modo che $ y != epsilon $ e che $ |xy| <= m $.
A questo punto posso affermare che la parola $ xz $ può essere del tipo $ 0^n 0^n $ oppure $ 0^(n-h) 1 0^n $ dove $ |y| =h $, poichè ho una y diversa dalla parola vuota, che sono entrambe parole che non appartengono al linguaggio, quindi ho trovato una falsità e posso concludere che il linguaggio non è regolare.
Qualcuno può controllare se il ragionamento e l'esercizio sono corretti? Ho alcuni dubbi...
1)L' n dell' esercizio si riferisce all'eventuale numero di stati che potrebbe avere l'automa nel caso di linguaggio regolare? O indica solamente in numero di 0?
2)E' giusto poter fissare la dimensione m dipendente da n?
3) Mi basta trovare solo una parola che viola il pumping lemma per definire il linguaggio non regolare?
Dimostrare che il seguente linguaggio non è regolare:
$ L=0^n 1 0^n | n >= 1 $
Suppongo che il linguaggio sia regolare.
Quindi prendo una parola $ |w|>m $ con $ m=2n+1 $.
Scompongo $ w $ in $ xyz $ in modo che $ y != epsilon $ e che $ |xy| <= m $.
A questo punto posso affermare che la parola $ xz $ può essere del tipo $ 0^n 0^n $ oppure $ 0^(n-h) 1 0^n $ dove $ |y| =h $, poichè ho una y diversa dalla parola vuota, che sono entrambe parole che non appartengono al linguaggio, quindi ho trovato una falsità e posso concludere che il linguaggio non è regolare.
Qualcuno può controllare se il ragionamento e l'esercizio sono corretti? Ho alcuni dubbi...
1)L' n dell' esercizio si riferisce all'eventuale numero di stati che potrebbe avere l'automa nel caso di linguaggio regolare? O indica solamente in numero di 0?
2)E' giusto poter fissare la dimensione m dipendente da n?
3) Mi basta trovare solo una parola che viola il pumping lemma per definire il linguaggio non regolare?
Risposte
"dandes92":
A questo punto posso affermare che la parola $ xz $ può essere del tipo $ 0^n 0^n $ oppure $ 0^(n-h) 1 0^n $ dove $ |y| =h $, poichè ho una y diversa dalla parola vuota...
"Uhm". E $y$ come è composta?
Partiamo dall'inizio: qual è la definizione di pumping lemma per linguaggi regolari che conosci?
"dandes92":
1)L' n dell' esercizio si riferisce all'eventuale numero di stati che potrebbe avere l'automa nel caso di linguaggio regolare? O indica solamente in numero di 0?
La seconda, è la usuale notazione per descrivere linguaggi infiniti: $A^k$ indica una stringa di $k$ simboli '$A$'.
"dandes92":
2)E' giusto poter fissare la dimensione m dipendente da n?
Da un certo particolare valore di $n$ o - equivalentemente - da una certa lunghezza in poi.
"dandes92":
3) Mi basta trovare solo una parola che viola il pumping lemma per definire il linguaggio non regolare?
Non ho capito cosa intendi.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo