Espressioni regolari

[stefano8612]

Ciao a tutti, ho bisogno di una mano per trovare le espressioni regolari di alcuni linguaggi.
Finché i linguaggi sono semplici sono in grado di trovarle, ma quando il linguaggio diventa più complicato ho qualche difficoltà.
Devo trovare l'espressione regolare di questi linguaggi:

  1. L = {w | w ∈ a*b* e |w|=2i+1, i ≥ 0}

  2. Insieme di stringhe con un numero uguale di 0 e 1 tale che in ogni prefisso la differenza tra il numero di 0 ed il numero di 1 è <2

  3. Espressione regolare che denota tutte le date nel formato gg/mm/aaaa tra 01/01/1900 e 2020/12/30. Supponiamo che tutti i mesi hanno 30 giorni.

  4. Espressione regolare sull'alfabeto {a, c} tale che non ci siano mai due o più di due 'a' consecutive e in cui le sequenze di 'c' consecutive siano di lunghezza pari

  5. Espressione regolare che denota l'insieme L di tutte le parole in alfabeto {a, b, c} in cui i simboli 'a' occorrono solo in termini di lunghezza pari.

  6. Espressione regolare denota l'insieme di tutte le parole sull'alfabeto {0,1,2} in cui non ci sono mai occorrenze consecutive di 0 (cioè le occorrenze di 0 sono sempre separate da almeno una occorrenza di 1 o di 0)

  7. Espressione regolare sull'alfabeto {a, b, c} denota il linguaggio L = {x | x in cui non ci sono mai le occorrenze 'aa', 'ab', 'ba', 'bb'}

  8. Espressione regolare che denota l'insieme di tutte le parole sull'alfabeto {a, b, c} dove non ci sono mai occorrenze consecutive 'c'

  9. Espressione regolare denota l'insieme di tutte le parole sull'alfabeto {a, b, c} con un numero dispari di 'b'

  10. espressione regolare che denota il linguaggio sull'alfabeto {a, b} costituito da tutte le stringhe che contengono esattamente un numero pari (anche 0) di 'a' e un numero arbitrario di 'b'

  Per il (3) ho pensato a: [(01)+(1(0..9))+(2(0..9))+30].[(0(1..9))+(1(0..2))].[(19(0..9)(0..9))+(20(0..2)(0..9))]
Ma mi sembra troppo complicato ..

So che sembrano dei compiti e in certo senso lo sono. Fra una settimana ho un esame e questi sono gli unici esercizi che non sono riuscito a risolvere e non so proprio come iniziare..

Il problema principale penso sia che per molti alcune occorrenze di caratteri possono trovarsi in qualsiasi punto della stringa..

Se sapete darmi qualche consiglio ve ne sarei molto grato.

Grazie!

[apatriarca]

Inizio a commentare il punto 3. Credo fosse esattamente il metodo che aveva in mente il tuo professore quando ti ha dato l'esercizio. Non è poi così tanto complicato dopotutto.. Vorrei solo aggiungere che non vedo i caratteri '/' che dovrebbero essere presenti tra le varie parti della data.. Perché hai usato '.' ?

Veniamo ora al primo esercizio. Il numero totale di caratteri della stringa deve essere dispari (oppure zero). Quindi, se il numero di 'a' è dispari, quello di 'b' deve essere pari e viceversa. La tua regex avrà quindi la forma (stringa vuota + (regex #'a' dispari) + (regex #'b' dispari)).

Per il secondo esercizio ti consiglio invece di cercare di costruire tali stringhe. Supponi ad esempio che la stringa inizi con un uno. Sai dire qualcosa del secondo carattere della stringa?