Espressioni Regolari e Grammatiche Context-Free

[AttraversamiIlCuore]

Ciao a tutti!
Mi serviva una mano su alcuni esercizi... molti sono riusciti a svolgerli (e volevo una conferma non avendo soluzioni) mentre altri mi serve qualche idea...

1) Scrivere Espressioni Regolari per :
- Alfabeto {0,1}, per tutte le stringhe che non terminano in "00"
(0|1)*(10|11|01) in quanto ho pensato che inizialmente può esserci qualsiasi cosa, ed ho obbligato gli ultimi due caratteri ad avere almeno un 1.

- Alfabeto {0,1}, per le stringhe con un numero pari di 0
Qui non ho idea :\ in quanto gli zeri possono stare in qualsiasi posizione, basta che siano pari

- Alfabeto {0,1}, per le stringhe con un numero di 0 maggiore di un numero di 1
Idem a sopra!

- Alfabeto {a,b}, parole di lunghezza dispari che finiscono per "aba"
(aa|bb|ab|ba|eps)*(aba)

- Alfabeto {a,b}, parole di lunghezza pari che iniziano per "aba" e NON terminano in "aba"
(aba)...

- Alfabeto {a,b}, parole di lunghezza multiplo di 3 che iniziano per "abb" e terminano in "bba"
(abb)(aaa|aab|aba|baa|abb|bba|bab|bbb)*(bba)

- Alfabeto {a,b}, parole di lunghezza multiplo di 3 che iniziano per "abb" e terminano in "bba" e contengono numero pari di "a"
(abb)(aab|aba|baa|aa)*(bba)

2) Scrivere Grammatiche contex-free

- Linguaggio $0^i 1^j$ con i=j $i,j >=0 $
S->0S1|01|eps

- Linguaggio $0^i 1^j$ con $0<=j<=2i $
Non saprei...

- Linguaggio delle parole del tipo $c* a^n b^n c*$
S->CAC
A->aAb|ab
C->eps|c|Cc

- Parole di lunghezza dispari che contengono "aba" al centro
S->AabaA
A->ab|bb|aa|ba|eps|bbA|aaA|abA|baA

-Parole che iniziano per $ a^n b^(2n) $ e finiscono èer bba
S->AB
A->abb|abbA
B->bba

Grazie mille anticipate!

[Rggb1]

"AttraversamiIlCuore":- Alfabeto {0,1}, per le stringhe con un numero pari di 0
Qui non ho idea :\ in quanto gli zeri possono stare in qualsiasi posizione, basta che siano pari

- Alfabeto {0,1}, per le stringhe con un numero di 0 maggiore di un numero di 1
Idem a sopra!

Non è molto difficile: sai schematizzare i DFA che riconoscono tali stringhe?

[AttraversamiIlCuore]

Allora, per il primo è facile. Visto che non ci sono restrizioni nel testo, assumo che sia possibile anche che non ci siano zeri.
Ho due stati (etichettiamoli 1 e 2). Dallo stato iniziale (che è anche finale) ho un arco etichettato con 0 che va nello stato 1, mentre l'arco etichettato con 1 rimane nello stato 1. Dallo stato 2, ho un arco etichettato con 0 che torna allo stato 1, e l'arco etichettato con 1 rimane nello stato 2.

Il secondo...mi verrebbe da risolverlo con l'automa a pila...

[Rggb1]

"AttraversamiIlCuore":Ho due stati (etichettiamoli 1 e 2). Dallo stato iniziale (che è anche finale) ho un arco etichettato con 0 che va nello stato 1, mentre l'arco etichettato con 1 rimane nello stato 1. Dallo stato 2, ho un arco etichettato con 0 che torna allo stato 1, e l'arco etichettato con 1 rimane nello stato 2.

Perfetto, ora da questo è facile creare una espressione regolare.

"AttraversamiIlCuore":Il secondo...mi verrebbe da risolverlo con l'automa a pila...

EDIT: mi sa che qui hai ragione, e quindi non c'è espressione regolare. Dove hai preso il testo?

[AttraversamiIlCuore]

Non avevo pensato a questa ipotesi perchè non abbiamo mai fatto l'algoritmo per passare da un automa a una espressione regolare (solo il contrario), ma sul libro l'ho trovato... ora do un'occhiata!
Questi testi li ho trovati in compiti di esame, ma non mi stupirei se fossero sbagliati -.-'
Oltre l'automa a pila, non saprei proprio come realizzarlo..
Intanto grazie per la disponibilità

[AttraversamiIlCuore]

Ho provato per l'ennesima volta e FORSE qualcosa ho tirato fuori...
Per il linguaggio $0^i 1^j ; i>=0 e 0<=j<=2i$
Diciamo che l'idea di base è quella, che per ogni 0 messo devo dare l'opportunità di mettere al massimo due 1 :
X->0XS|0S|eps
S->1|11|eps

Per il linguaggio $0^i 1^j$ con numero di 0 maggiore del numero di 1
Q->0Q1|R
R->0R|0

Che dite?!