Benvenuto!
Accedi
o
registrati
.
26-04-2018, 18:08:06
Home
CDL Informatica
UniCT
CEA
Prof
Help
Search
Calendar
Login
Register
Forum Informatica Unict
»
LAUREA TRIENNALE (D.M. 270/04)
»
I anno
»
Fondamenti di Informatica, 9 CFU
(Moderators:
Giuseppe Scollo
,
Marina Madonia
,
Franco Barbanera
) »
pumping lemma
Pages: [
1
]
Go Down
« precedente
successivo »
Print
Author
Topic: pumping lemma (Read 368 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Gerasia
Matricola
Offline
Posts: 29
pumping lemma
«
on:
10-01-2018, 18:10:09 »
ho provato a fare questo esercizio sul pumping lemma, qualcuno potrebbe dirmi se è corretto o meno??
L={a
n
b
n
|n>=0}
pongo come ipotesi:
n=3 x=aabb
adesso verifico le proprietà(
) del pumping lemma:
|uv|=|aa|<3
|v|=1
X
i
0
=uv
0
z
X
i
0
=abb che non appartiene al linguaggio,
quindi posso affermare che il linguaggio L={a
n
b
n
|n>=0} non è un linguaggio regolare
Logged
teo998
Matricola
Offline
Posts: 42
Re:pumping lemma
«
Reply #1 on:
11-01-2018, 18:19:08 »
non credo si possa porre n a piacere, perché il suo valore dipende dall'automa che riconosce il linguaggio
puoi porre x a piacere, chiaramente in funzione della variabile n
l'esercizio comunque è svolto nell'ausiello
Logged
Link Immagine
Link Immagine
Gerasia
Matricola
Offline
Posts: 29
Re:pumping lemma
«
Reply #2 on:
11-01-2018, 19:54:09 »
infatti ho messo n=3 apposta perchè è il numero degli stati dell'automa
Logged
ScavoRosario98
Matricola
Offline
Posts: 4
Re:pumping lemma
«
Reply #3 on:
11-01-2018, 20:45:17 »
Provo a risolverlo ma non garantisco la correttezza dello svolgimento.
Dato il linguaggio
Deduco che il 'numero di a' deve essere uguale al 'numero' di b.
Per dimostrare che il linguaggio non è regolare, utilizzo il pumping lemma, ovvero, devo negarlo, questo significa:
|z|>=n
quindi in uv avrò tutte a mentre in w avrò tutte b, nello stesso numero.
Prendendo però i=0
, in quanto in quanto modo so sicuramente che ci saranno n volte caratteri b ma al più n caratteri di a.
Sperò di non aver detto troppe scemenze
Logged
Franco Barbanera
Moderator
Forumista Eroico
Offline
Posts: 2.918
Re:pumping lemma
«
Reply #4 on:
11-01-2018, 21:09:51 »
Quote from: Gerasia on 11-01-2018, 19:54:09
infatti ho messo n=3 apposta perchè è il numero degli stati dell'automa
Da dove salta fuori il numero 3???
Logged
teo998
Matricola
Offline
Posts: 42
Re:pumping lemma
«
Reply #5 on:
12-01-2018, 10:18:38 »
Quote from: Gerasia on 11-01-2018, 19:54:09
infatti ho messo n=3 apposta perchè è il numero degli stati dell'automa
così hai dimostrato che non esiste un automa con 3 stati che riconosce il linguaggio; per dimostrare che è non regolare devi dimostrare che per qualunque valore di n non esiste un ASFD che lo riconosca
Logged
Link Immagine
Link Immagine
Gerasia
Matricola
Offline
Posts: 29
Re:pumping lemma
«
Reply #6 on:
12-01-2018, 10:49:28 »
Quote from: teo998 on 12-01-2018, 10:18:38
Quote from: Gerasia on 11-01-2018, 19:54:09
infatti ho messo n=3 apposta perchè è il numero degli stati dell'automa
così hai dimostrato che non esiste un automa con 3 stati che riconosce il linguaggio; per dimostrare che è non regolare devi dimostrare che per qualunque valore di n non esiste un ASFD che lo riconosca
io avevo capito si potesse scegliere un valore tenendo conto del numero minimo degli stati che servono ad un automa per riuscire a riconoscerlo o meno
Logged
jeremy_sapienza
Matricola
Offline
Posts: 11
Re:pumping lemma
«
Reply #7 on:
12-01-2018, 12:18:01 »
Quote from: Gerasia on 12-01-2018, 10:49:28
Quote from: teo998 on 12-01-2018, 10:18:38
Quote from: Gerasia on 11-01-2018, 19:54:09
infatti ho messo n=3 apposta perchè è il numero degli stati dell'automa
così hai dimostrato che non esiste un automa con 3 stati che riconosce il linguaggio; per dimostrare che è non regolare devi dimostrare che per qualunque valore di n non esiste un ASFD che lo riconosca
io avevo capito si potesse scegliere un valore tenendo conto del numero minimo degli stati che servono ad un automa per riuscire a riconoscerlo o meno
se avesse detto, fissato un numero k era in quel modo
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
Offline
Gender:
Posts: 4.464
Più grande è la lotta, e più è glorioso il trionfo
Re:pumping lemma
«
Reply #8 on:
12-01-2018, 15:18:51 »
Quote from: Gerasia on 11-01-2018, 19:54:09
infatti ho messo n=3 apposta perchè è il numero degli stati dell'automa
Quale automa? Quello che non esiste?
Qui adesso risulta agevole utilizzare la funzione Ricerca (Search in alto) di questo forum, per poterti indirizzare a
questo mio interessante post a riguardo del Pumping Lemma
.
Leggi, studia, e chiedi scusa
...
«
Last Edit: 12-01-2018, 15:37:55 by ɹǝǝuıƃuǝsɹǝʌǝɹ
»
Logged
La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.
In tutto, amare e servire.
✚
ن
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...
...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...
▶
YouTube
❾
9GAG
ⅱ
anobi
i
S
Steam
☺
T.B.o.I. Wiki
[
]
Lezioni private
ʼ
Albo d'Ateneo
Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il
Regolamento
teo998
Matricola
Offline
Posts: 42
Re:pumping lemma
«
Reply #9 on:
12-01-2018, 17:18:43 »
Quote from: Gerasia on 12-01-2018, 10:49:28
io avevo capito si potesse scegliere un valore tenendo conto del numero minimo degli stati che servono ad un automa per riuscire a riconoscerlo o meno
quello che hai scritto è vero; il fatto è che questo numero minimo degli stati che servono ad un automa per riconoscere un linguaggio non è noto a priori; potrebbe essere uno, cento, centomila
Per fare il ragionamento che hai fatto tu dovresti prima dimostrare che il numero minimo degli stati necessari è 3 (ma dimostrare questo non è possibile)
Logged
Link Immagine
Link Immagine
Pages: [
1
]
Go Up
Print
« precedente
successivo »
Jump to:
Please select a destination:
-----------------------------
Area Ufficiale
-----------------------------
=> Annunci Ufficiali
=> Segreteria Didattica
=> Aiuto, proposte e commenti
=> Stages e progetti finali
=> C.O.F. Centro Orientamento e Formazione
=> Messaggi (d)agli amministratori del forum
-----------------------------
LAUREA TRIENNALE (D.M. 270/04)
-----------------------------
=> I anno
===> Architettura degli Elaboratori, 9 CFU
===> Elementi di Analisi Matematica, 12 CFU
===> Fondamenti di Informatica, 9 CFU
===> Matematica Discreta, 12 CFU
===> Programmazione 1, 9 CFU
===> Programmazione 2, 9 CFU
=> II anno
===> Algoritmi, 9 CFU
===> Basi di Dati, 9 CFU
===> Fisica, 9 CFU
===> Ingegneria del Software, 9 CFU
===> Inglese, 3 e 6 CFU
===> Interazione e Multimedia, 9 CFU
===> Sistemi Operativi, 9 CFU
=> III anno
===> Calcolo Numerico, 6 CFU
===> Formazione Numerica, 6 CFU
===> Introduzione all'Analisi dei Dati, 9 CFU
===> Metodi Matematici e Statistici, 6 CFU
===> Reti di Calcolatori, 9 CFU
===> Tecniche di Programmazione Concorrente e Distribuita, 9 CFU
===> Teoria dell'Informazione e Crittografia, 9 CFU
=> III anno - Materie a scelta (crediti liberi)
===> Computer Forensics, 6 CFU
===> Computer Graphics, 9 CFU
===> Digital Game Development, 6 CFU
===> GPGPU/CUDA, 6 CFU
===> Informatica Musicale, 6 CFU
===> LAP 1: programmazione C/C++ 6 CFU
===> LAP 2: Programmazione Android, 6 CFU
===> Sistemi Centrali, 6 CFU
===> Startup d'impresa e Modelli di Business, 6 CFU
===> Internet Security 9 CFU
===> Social Media Management, 6 CFU
=> Corsi disattivati - Vecchio curriculum
===> E-Commerce, 6 CFU
===> Legislazione Informatica, 6 CFU
===> Teoria della Computabilità, 9 CFU
-----------------------------
LAUREA MAGISTRALE
-----------------------------
=> I ANNO
===> Intelligenza Artificiale e Lab, 9 CFU
===> Algoritmi e Complessità, 9 CFU
===> Computer Vision, 9 CFU
===> Crittografia, 9 CFU
===> Fondamenti e Linguaggi per la Programmazione Distribuita
===> Inglese Scientifico, 3 CFU
===> Metodi analitici per l'informatica, 6 CFU
===> Metodi Matematici per l'Ottimizzazione (Corso Integrato), 12 CFU
===> Multimedia, 9 CFU
===> Sicurezza dei Sistemi Informatici 9 CFU
===> Computer Security, 9 CFU
=> II ANNO
===> Machine Learning 6 CFU
===> Teoria della Computabilità, 9 CFU
===> Analisi e Gestione dei Dati, 9 CFU
===> Compilatori, 9 CFU
===> Computazione Naturale e BioIspirata, 6 CFU
===> Introduzione alla Bioinformatica, 9 CFU
===> Linguaggi Formali e Applicazioni, 9 CFU
===> Logica Computazionale, 9 CFU
===> P2P & Wireless Networks, 9 CFU
===> Pattern Recognition, 9 CFU
===> Sistemi Distribuiti, 9 CFU
===> Sistemi dedicati e laboratorio, 9 CFU
===> Web Reasoning
=> Corsi disattivati - Vecchio curriculum
===> Fisica moderna per l'informatica, 6 CFU
===> Linguaggi di Programmazione, 9 CFU
===> Protocolli di Rete
===> Teoria dei Codici, 6 CFU
-----------------------------
Vecchi ordinamenti ad esaurimento
-----------------------------
=> Laurea Triennale (D.M. 509/00)
===> Algoritmi 1
===> Algoritmi 2
===> Basi Teoriche dell'Informatica
===> Economia Aziendale
===> Fisica 1, 6 CFU
===> Fisica 2, 6 CFU
===> Fisica 3
===> Formazione Analitica 1
===> Formazione Analitica 2
===> Formazione Discreta 1
===> Formazione Discreta 2
===> J2ME
===> Lab. Amministrazione di Sistemi
===> Laboratorio di Interazione
===> Modelli Matematici
===> Multimedia per Dispositivi Mobile
===> Progetto Software
===> Reti 1, 6 CFU
===> Sicurezza dei Sistemi Informatici 1
===> Sistemi Distribuiti 1
===> Teoria dei Grafi
===> Usabilità ed Estetica del Web
===> Web Programming
=> Laurea Specialistica (D.M. 509/00)
===> Algoritmi 3
===> Analisi Numerica
===> Complessità
===> Computabilità
===> Data analysis e management
===> Ingegneria del software 2
===> Linguaggi Formali
===> Metodi algoritmici per l'ottimizzazione combinatoria
===> Programmazione Funzionale
===> Reti di Calcolatori 2
===> Ricerca Operativa
===> Sistemi Distribuiti 2
-----------------------------
Dottorandi
-----------------------------
=> Wall
=> Events
-----------------------------
Area Studenti
-----------------------------
=> Agorà
=> L'angolo del tecnico
=> Il Mercatino degli studenti
=> Software
===> -vecchia catalogazione [sarà rimossa a breve]-
=====> Proprietario
=====> Free Software
=====> Open Source
===> Approfondimenti
===> News
===> Studio
===> Videogiochi
===> Networking e telecomunicazioni
===> Sviluppo
===> Ufficio e produttività
===> Sistemi Operativi
=====> Microsoft Windows
=====> GNU/Linux, Unix e BSD
=====> Mac OS X
=====> Windows Phone
=====> Android
=====> iOS
=====> Altri
===> Eventi, conferenze, concorsi
=> Microsoft Student Partner - Avvisi e informazioni
=> ERASMUS/borse di studio internazionali
Caricamento in corso...