ESERCIZI DI CALCOLABILITA E COMPLESSITA

RIGELS ZYFERI Mat: 693236

10/11/2005

Serie B

E' vero che ogni sottinsieme di un insieme regolare è regolare? Si motivi la risposta.

L' affermazione che ogni sottinsieme regolare è regolare è falso, perche se consderiamo ∑*

il linguaggio regolare che contiene tutte le stringhe possibili sull' alfabeto ∑, allora avvevamo

che tutti i linguaggi sono regolari, ma sappiamo che questo è falso sicome esistono dei

linguaggi non regolari come per esempio anbn, per ogni n>=0.

E' possibile costruire un automa a stati finiti deterministico con દ-mosse? Se la risposta è si, si dia la costruzione, altrimenti si motivi la risposta.

Per la definizione dell' automa a stati finiti deterministico (DFA) segue che:

Un automa a stati finiti deterministico è una 5-tupla (Q, ∑, δ, q, F), dove

Q è un insieme finito di stati.

∑ è un insieme finito di caratteri.

δ:Qx∑ --> Q é la funzione di transizione.

q∈Q è il stato di partenza.

F⊂Q è l'insieme di stati finiti o di accettazione.

Con la definizione data si capisce che per ogni stato in Q e per un dato elemento

dell alfabeto ∑ non esistono piu di una transizione per quell elemento e non esitono

nessun દ-mosse sicome {દ} non appartiene a ∑.

Dal definizione precedente segue che non è possibile costruire un automa a stati finiti	deterministico con દ-mosse, ma se estendiamo la funzione di transizione δ dal dominio

Qx∑ al dominio Qx∑* cioè δ* :Qx∑*-->Q, definito ricorsivamente come segue:

Base: Se |x|=0, allora δ*(q,x)=q

Passo ricorsivo: Se |x|>0, allora x=ya t.c y∈∑* e a∈∑ consideriamo il seguento caso.

δ*(q,x)=δ(δ*(q,y),a)

Notiamo che δ(q,a)=δ*(q,a), per ogni a∈∑.

E definiamo l'accettazione come segue:

z∈∑* è accettata da un DFA B se δ*(q,z)∈F, dove q è lo stato iniziale.

Allora possiamo dire che siamo arrivati a costruire un automa deterministico con દ-mosse,

sicome considerando la base della definizione del funzione ricorsivo di transizione {દ}∈∑*,

e per ogni stato dell' automa abbiamo un દ-mossa in se stesso.

Si dimostri, usando il pumping lemma, che il linguaggio delle parole palindrome su {0,1}non è

regolare.

Definiamo il linguaggio dei palindromi come Pal={s∈{a,b}* | s=reverse(s)}, dove

reverse(દ)=દ , reverse(a1..... an)= an....... a1

Per dimostrare con “Pumping Lemma” che il linguaggio Pal non è regolare, dobbiamo assumere

che Pal è regolare per ottenere la contradizione.

Sia p un qualsiasi intero, consideriamo s=apbap, per la definizione del linguaggio Pal, s∈Pal e	per uno dei criteri di Pumping Lemma |s|>=p.

Consideriamo la scomposizione di s come s=xyz dove |y|>=1 e |xy|<=p .

Allora denotiamo x=ar e y=as con r>=0,1<=s<=k. Sicome r+s<=k, esiste t>=0 t.c r+s+t=k .

Considerando xyyz =xy2z=ar a2satbak, dove z=atbak non appartiene al Pal perche r+2s+t non è

uguale a k. Segue la contradizione che Pal è regolare, cioè finalmente Pal non è regolare.

2005-11-08T00:41:46