Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Fondamenti di Informatica, 9 CFU => Topic started by: Sain on 08-11-2018, 16:48:45



Title: Esercizio 23 - Linguaggi Formali
Post by: Sain on 08-11-2018, 16:48:45
Nell'esercizio 23 nella pagina degli esercizi sui linguaggi formali viene chiesto se il linguaggio {anbm|n ≥k, m≥ k} è regolare prendendo un k qualsiasi.


Per dimostrare che un linguaggio è regolare, è sufficiente scrivere una espressione regolare che lo generi.

(Caso generale):
Una espressione regolare che genera il suddetto linguaggio è:
aka*bkb*  per ogni k∈N.

(Casi particolari):
Prendo un k qualsiasi, ad esempio k=0.
Una espressione che genera il linguaggio {anbm|n ≥0, m≥ 0} è:
a0a*b0b*=a*b*.

Prendo k=1.
Una espressione che genera il linguaggio {anbm|n ≥1, m≥ 1} è:
a1a*b1b*.

Continuando così per ogni k∈N.


A questo punto mi chiedo una cosa: in questo esercizio è corretto dimostrare che il linguaggio è regolare attraverso il "caso generale" oppure basta prendere un caso particolare (in cui k assume un valore qualsiasi)?


Title: Re:Esercizio 23 - Linguaggi Formali
Post by: Franco Barbanera on 08-11-2018, 17:52:12
Quello che tu chiami "caso generale" va benissimo.
I "casi particolari" sono inutili.

Al posto pero' di dire

Una espressione regolare che genera il suddetto linguaggio è:
aka*bkb*  per ogni k∈N.

E' meglio scrivere:

Preso  k∈N,
una espressione regolare che genera il suddetto linguaggio è:
aka*bkb*

FB


Title: Re:Esercizio 23 - Linguaggi Formali
Post by: Sain on 08-11-2018, 18:05:03
Grazie tante!