Pages: [1]   Go Down
Print
Author Topic: Esercizio 22 linguaggi formali  (Read 386 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Ecosentino
Matricola
*
Offline Offline

Gender: Male
Posts: 13


« on: 22-02-2017, 19:03:05 »

Dimostrare che per ogni possibile k il linguaggio
{anbn | n ≤k}
è regolare.

Per farlo dimostriamo che, comunque fissato k, esiste un'espressione regolare che rappresenta il linguaggio ottenuto.

Caso base: k = 0
{anbn | n ≤ 0}
abbiamo quindi che n = 0, quindi il linguaggio si riduce alla stringa
a0b0 = ε
che è rappresentabile dall'espressione regolare
*

Caso induttivo: {anbn | n ≤ k+1}
Abbiamo che
{anbn | n ≤ k + 1} = {anbn | n ≤ k} U {anbn | n = k + 1} = {anbn | n ≤k} U {ak +1bk + 1}
Il primo linguaggio è regolare per ipotesi induttiva, il secondo linguaggio è regolare perché, utilizzando per semplicità la notazione esponenziale, esso è rappresentabile dall'espressione regolare
ak +1bk + 1
Poiché l'unione di 2 linguaggi regolare è anch'essa un linguaggio regolare (Teorema 3.6 Ausiello) la dimostrazione è completa.


Più semplicemente fissato un qualunque k, il linguaggio
{anbn | n ≤k}
è rappresentabile dall'espressione regolare
a0b0 + a1b1 + ... + akbk
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.794



WWW
« Reply #1 on: 22-02-2017, 22:18:09 »

Fantastico!

Bastava anche la seconda risposta proposta.
Ma la dimostrazione formale per induzione matematica su k e' una gioia per
lo spirito.
Logged
Pages: [1]   Go Up
Print
Jump to: