[Informatica Teorica]Tecnica per fare le regole di produzione per un linguaggio

[fbcyborg]

Ciao a tutti,

premetto che sono un po' una zappa in materia e faccio un po' di difficoltà a masticare queste cose.

Mi sto accingendo a studiare dei corsi di informatica teorica e comincio ad avere qualche difficoltà su cose che del resto ho già studiato in precedenza (fatte male, molto male ma non per colpa mia). Ora mi trovo di fronte ad un problema: esiste una tecnica per generare le regole di produzione per un linguaggio?

Ad esempio, sul mio libro di "Linguaggi e Sistemi Formali" ho un esempio che dice più o meno questo: Scrivere le regole di produzione dato il linguaggio L={w | w ha lo stesso numero di 0 e di 1}.

La soluzione diciamo che la capisco; il problema è che molto probabilmente se tentassi di farlo da solo ci impiegherei un giorno intero e magari non darei nemmeno la soluzione corretta.
Questo implica che io sto sbagliando approccio per affrontare questo problema.

C'è qualcuno che possa indirizzarmi per capire meglio come affrontare questo tipo di problema?

Grazie

[netsky3]

mi iscrivo =)

[vegeta83ssj]

Originariamente inviato da fbcyborg

Ciao a tutti,

premetto che sono un po' una zappa in materia e faccio un po' di difficoltà a masticare queste cose.

Mi sto accingendo a studiare dei corsi di informatica teorica e comincio ad avere qualche difficoltà su cose che del resto ho già studiato in precedenza (fatte male, molto male ma non per colpa mia). Ora mi trovo di fronte ad un problema: esiste una tecnica per generare le regole di produzione per un linguaggio?

Ad esempio, sul mio libro di "Linguaggi e Sistemi Formali" ho un esempio che dice più o meno questo: Scrivere le regole di produzione dato il linguaggio L={w | w ha lo stesso numero di 0 e di 1}.

La soluzione diciamo che la capisco; il problema è che molto probabilmente se tentassi di farlo da solo ci impiegherei un giorno intero e magari non darei nemmeno la soluzione corretta.
Questo implica che io sto sbagliando approccio per affrontare questo problema.

C'è qualcuno che possa indirizzarmi per capire meglio come affrontare questo tipo di problema?

Grazie

Dai una letta alle slide del prof. che mi ha fatto il corso di linguaggi a bologna, imho sono ben fatte e comprensibili.

Il tuo esempio di linguaggio dovrebbe essere di tipo 2 secondo chomsky con self-embedding ma essendo passato più di un anno non ti garantisco nulla!
Visto come espressione regolare una roba tipo questa: 0^n 1^n

Ciauz

[fbcyborg]

Ciao ragazzi, grazie mille per gli interventi.
Sì, in effetti cerco qualcosa di teorico. E devo imparare a scrivere le produzioni dati determinati requisiti.

vegeta83ssj, per favore mi dai un link a queste slide che hai citato?

[vegeta83ssj]

Originariamente inviato da fbcyborg

Ciao ragazzi, grazie mille per gli interventi.
Sì, in effetti cerco qualcosa di teorico. E devo imparare a scrivere le produzioni dati determinati requisiti.

vegeta83ssj, per favore mi dai un link a queste slide che hai citato?

OPS!
http://edenti.deis.unibo.it/Ling/2006-2007/Slide.html

Mi ero scordato il link!

[fbcyborg]

Grazie, vedo subito.

[suspence]

beh, da reminescenze di linguaggi e traduttori, dovresti crearti l'automa che ti riconosce una determinata sequenza e poi da lì l'espressione regolare che la rappresenta...

[vegeta83ssj]

Originariamente inviato da suspence

beh, da reminescenze di linguaggi e traduttori, dovresti crearti l'automa che ti riconosce una determinata sequenza e poi da lì l'espressione regolare che la rappresenta...

Esatto!
E dall'automa alle produzioni diventa un passaggio banale e meccanico.

[pietro84]

esiste il thread apposito per informatica teorica... è anche tra quelli in primo piano

[fbcyborg]

Originariamente inviato da suspence

beh, da reminescenze di linguaggi e traduttori, dovresti crearti l'automa che ti riconosce una determinata sequenza e poi da lì l'espressione regolare che la rappresenta...

Ok, e supponiamo per un momento che oggi ancora non siamo arrivati a fare gli ASF, e che mi si chieda di scrivere le produzioni di un linguaggio senza ricorrere agli automi... come fare? A caso? A tentativi e poi verifico se funziona?

@pietro84: grazie. Se vuoi puoi anche portare un contributo utile alla risoluzione di questa questione.

[magix2003]

Ciao,
io sto preparando proprio ora l'esame di linguaggi formali. Ovviamente non devi andare a caso, ma ad intuito. A parer mio non c'è un metodo preciso, devi pensare ad un istanza del linguaggio e provare a caratterizzarla.

[netsky3]

Originariamente inviato da magix2003

Ciao,
io sto preparando proprio ora l'esame di linguaggi formali. Ovviamente non devi andare a caso, ma ad intuito. A parer mio non c'è un metodo preciso, devi pensare ad un istanza del linguaggio e provare a caratterizzarla.

che facoltà sei?

[magix2003]

che facoltà sei?

Informatica applicata alla Libera università di Bolzano.

[pietro84]

@pietro84: grazie. Se vuoi puoi anche portare un contributo utile alla risoluzione di questa questione.

ci sono utenti più esperti di me in materia(tipo Morkar), che probabilmente ti avrebbero risposto da tempo se avessi scritto nel thread apposito .
era solo un consiglio per farti avere una risposta di migliore qualità e forse in tempi più rapidi. non era un tono polemico il mio .

[fbcyborg]

Giusto per ritornare in discussione.. a titolo di esempio mi aiutate a capire come risolvere il seguente esercizio??? Devo imparare a ragionarci su, non sono nato imparato:

Definire una grammatica che generi il linguaggio {} e dimostrare la sua correttezza.

[Ziosilvio]

Originariamente inviato da fbcyborg

Scrivere le regole di produzione dato il linguaggio L={w | w ha lo stesso numero di 0 e di 1}.

Originariamente inviato da pietro84

esiste il thread apposito per informatica teorica... è anche tra quelli in primo piano

Già, e si trova QUI.

[fbcyborg]

Vabbè...

allora faremo crossposting.. l'avete detto voi eh.
Fra l'altro sono anche iscritto a quel thread.. che dite, l'avrò visto?????

[fbcyborg]

Originariamente inviato da suspence

beh, da reminescenze di linguaggi e traduttori, dovresti crearti l'automa che ti riconosce una determinata sequenza e poi da lì l'espressione regolare che la rappresenta...

Riprendo un attimo da ciò che mi hai detto perché facendo degli esercizi di base mi sono trovato ancora un po' in difficoltà. Dunque, se ad esempio dovessi definire la grammatica che genera il linguaggio formato da {a,b} il cui numero di a sia dispari, non avrei difficoltà. Partendo dall'automa a stati finiti mi disegno 2 stati e poi riesco a scrivere le regole di produzione.

Ma nel caso in cui la cosa fosse un po' più complicata come ad esempio "scrivere le regole di produzione per la grammatica che genera il linguaggio , non saprei proprio come fare. Dite che si può "sempre" fare il diagramma degli stati per un ASF??

[magix2003]

Non puoi creare un ASF per tutti i linguaggi, ma solo per quelli regolari. Quindi, se hai il linguaggio L = {a^n b^ m | n = m} non potrai mai rappresentarlo attraverso un ASF, devi per forza utilizzare una grammatica.