Creeaza.com - informatii profesionale despre


Evidentiem nevoile sociale din educatie - Referate profesionale unice



Acasa » referate » informatica
Limbaje regulate

Limbaje regulate





LIMBAJE REGULATE

  1. Exemple practice de automate finite deterministe (AFD);
  2. Definitia formala a unui AFD,

moduri de descriere;

limbaj recunoscut de un AFD

  1. O metoda de definire a unui AFD care sa recunoasca un limbaj dat
  2. Lema de pompare pentru limbaje regulate
  3. Automate finite nedeterministe

definitie

echivalenta

  1. Operatii de inchidere (regulate)
  2. Expresii regulate

definitie

echivalenta

Diferentele dintre un AFD si un AFN sunt:

1)     ' ' qIQ: pentru fiecare simbol aIS:

in AFD pleaca o singura sageata,

0,

in AFN pleaca 1, sau

mai multe sageti;

2)     Sagetile sunt etichetate:

in AFD: cu simboluri din S,

cu simboluri din S,

in AFN: cu simbolul vid, l.

3)     Modul de calcul

Definitie

AFN = (Q, S, d, q0, F), unde:

Q = multime finita, nevida, ale carei elemente se numesc stari;

S = multime finita, nevida, numita alfabet de intrare, ale carei elemente se numesc simboluri;

d : Q x (S ) P(Q), numita functia de tranzitie;

q0 IQ, numita starea initiala;

FQ numita multimea starilor finale.

Notatie

Sl = S )

Exemplu

AFN care recunoaste limbajul:

L2=

Teorema

AFN AFD

Corolar

' LS*, LIL3: $ AFN care recunoaste L.

Definitie

Operatii de inchidere = operatii regulate =

    • reuniunea,
    • concatenarea,
    • operatia star (*).

Teorema

L3 este inchisa la reuniune, concatenare, operatia star.

Definitie

Expresie regulata =

o expresie R care satisface una dintre urmatoarele conditii:

  1. 'aIS este o expresie regulata (reprezentand limbajul S*);
  2. l este o expresie regulata (reprezentand limbajul S*);
  3. este o expresie regulata (reprezentand limbajul vid);
  4. daca R1 si R2 sunt expresii regulate T

       (R1R2) este o expresie regulata,

       (R1oR2) este o expresie regulata,

       (R1*) este o expresie regulata.

Exemplu

(01)0*

Teorema

' LS*, LIL3: $ o expresie regulata R peste S care descrie L.

Definitie

AFNG = (Q, S, d, qstart, qaccept), unde:

Q = multime finita, nevida, ale carei elemente se numesc stari;

S = multime finita, nevida, numita alfabet de intrare, ale carei elemente se numesc simboluri;

qstart IQ, numita starea initiala;

qaccept IQ, numita starea finala;

d : (Q ) x (Q ) R, numita functia de tranzitie.

CURS 2

LIMBAJE INDEPENDENTE DE CONTEXT (RECAPITULARE)

1. Definitii

gramatica

gramatica independenta de context

limbaj independent de context

2. Forme normale

definitie

exemple

aducerea la forma normala Chomsky

3. Lema de pompare

4. Operatii de inchidere

L2 este inchisa la reuniune, concatenare, operatia *, omomorfism

L2 nu este inchisa la intersectie si complementara

5. Automatul pushdown

  • memoria finita a unui AFD nu poate memora numere n foarte mari.
  • gramaticile independente de context (GIC)
  • structura recursiva
  • Domenii de utilizare a GIC:
    • studiul limbilor naturale,
  • Domenii de aplicabilitate
    • specificarea si compilarea limbajelor de programare
    • sintaxa unui limbaj de programare
    • parsere

Nota:

Desi AFD si EXPR REG pot descrie un numar mare de limbaje, exista si limbaje - unele chiar destul de simple pe care nu le pot descrie:

EX:

Motivul: memoria finita a unui AFD nu poate memora numere n foarte mari.

Un mecanism mai puternic este cel al GRAMATICILOR INDEPENDENTE DE CONTEXT (GIC)

Ele pot descrie unele aspecte care au o STRUCTURA RECURSIVA, fiind astfel utile intr-o varietate de domenii:

1) Un exemplu de UTILIZARE a GIC: STUDIUL LIMBILOR NATURALE.

Relatii dintre termeni precum: substantiv, verb, adjectiv, prepozitie, precum si dintre expersii substantivale, verbale etc. sunt in mod natural de tip recursiv:

O expresie verbala poate contine o expersie substantivala (de ex.) care, la randul ei, poate contine o expresie verbala sau adjectivala etc. Oei, o GIC poate modela in mod convenabil astfel de situatii

2)     Un exemplu de APLICARE a GIC: SPECIFICAREA SI COMPILAREA LIMBAJELOR DE PROGRAMARE.

        Sintaxa unui limbaj de programare poate fi invatata si pornind de la gramatica acestuia.

Proiectarea compilatoarelor si interpretoarelor de lb. de progr. Incepe deseori cu construirea unei GIC pt acel lb.

        Cele mai multe compilatoare si interpretoare contin o componenta, numita PARSER, care extrage semnificatia unui program chiar inainte ca ca respectivul cod sa fie compilat sau ca instructiunea interpretata sa fie executata.

Acest proces de extragere a semnificatiei din codul programului se n. PARSING si permite traducerea codului scris intr-un lb. de progr. de nivel inalt intr-o forma mai adecvata executarii de catre calculator.

        O posibila reprezentare a acestei semnificatii este arborele de derivare al codului (PARSING TREE) obtinut cu ajutorul GIC a lb. de progr. respectiv.

        Exista numeroase metodologii care permit construirea uneori automat a unui parser direct din GIC a lb. de progr.

Reamintim ca:

  1. Limbajele generate / descrise de G.I.C. se numesc L.I.C.;
  2. Clasa L2 L3;
  3. Un mecanism, care s-a dovedit a fi echivalent cu cel al G.I.C., este constituit de APD.

Definitia 1

Gramatica = (V,S, P, S) unde:

V = multime finita, nevida, ale carei elemente se numesc variabile sau neterminale;

S = multime finita, nevida, numita alfabet de intrare, ale carei elemente se numesc terminale; VS=;

P = multime finita, nevida, ale carei elemente se numesc productii sau reguli de substitutie;

(ele descriu modul in care o variabila poate fi inlocuita cu o secventa de terminale si neterminale);

SIV se numeste variabila (simbolul) de start.

Exemplu

G1=(, , , A)

Reprezentarea derivarilor:

  • linear:

AT0A1T00A11T000A111T03B13T03#13

  • sintetic:

A GT* 03#13

  • arbore de derivare:

Nota:

Exemplu

G1=(, , , A)

O gramatica va calcula astfel:

P1) incepe cu productia / una dintre productiile in care in m.stg. apare smb. de start si inlocuieste smb. de start cu secventa din m. dr. ;

P2) alege o variabila din acest m.dr. si

o productie care contine acea variabila in m. sau stg.

si o inlocuieste cu m.dr. al acelei productii;

P3) se reia (Pasul 2) pana cand in m.dr. avem doar terminale.

Acest proces se numeste derivare si se poate reprezenta in mai multe moduri:

linear:

AT0A1T00A11T000A111T03B13T03#13

sintetic:

A T* 03#13

arbore de derivare

o derivare se incheie atunci cand frunzele arborelui de derivare sunt etichetate numai cu terminale.

Definitia 2

Gramatica independenta de context = (V,S, P, S) a.i.

' ab I P: |a|=1 si a I V.

Definitia 3

Limbaj independent de context = L.I.C. =

L(G)=

Exemplu

G2=(, , , S) T

L2=.

Nota:

Definitia 2

Gramatica independenta de context =

o gramatica G=(V,S, P, S) in care fiecare productie are in m.stg. 1! singura variabila. .

Definitia 3

Limbaj independent de context = L.I.C. =

limbajul descris de o G.I.C. ..

Exemplu

G2=(, , , S) T ..

Limbajul parantezelor bine imbricate

Definitia 4

G I G.I.C. se afla in forma normala GREIBACH (FNG)

' p I P, p : A aB, unde:

A I V,

a I S

B I (V S)*.

Teorema 1

' L=L(G) I L.I.C., l L: $ G in FNG a.i. L=L(G).

Nota:

F.N. sunt standardizari ale GIC care faciliteaza anumite prelucrari, demonstratii, aplicari de algoritmi etc. Definitia 4

Definitia 4

G I G.I.C. se afla in forma normala GREIBACH (FNG)

orice productie din P este de forma A aB, unde: A I V,

a I S

B I (V S)*.

Teorema 1

Orice LIC care nu contine cuvantul vid, poate fi generat de o GIC aflata in FNG.

Definitia 5

G I G.I.C. se afla in forma normala CHOMSKY (FNC)

' p I P, p : A BC sau A a, unde:

A,B,C I V, B S C,

a I S,

In plus, S l I P.

Lema 1 (demonstratia: EXERCITIU)

Fie G I G.I.C. aflata in FNC si L = L(G) T

'wIL, |w|=n: ' |S GT*w| = 2n-1, n I N.

Nota:

Definitia 5

G I G.I.C. se afla in forma normala CHOMSKY (FNC)

' productie din P ested e forma A BC sau A a, unde:

A,B,C I V, B S C,

a I S,

In plus, se admite productia S l.

Lema 1

Fie L un LIC generat de o GIC aflata in FNC.

Atunci, lungimea oricarei derivari pentru un cuvant de lungime n este de 2n-1 .

Teorema 2

L=L(G) I L.I.C.: $ G in FNC a.i. L=L(G).

Demonstratie

Fie G = (V,S, P, S), L = L(G); construim G= (V0,S0, P0, S0), echivalenta, in FNC.

(P1) adaugam un nou simbol de start S0 si

o noua productie: S0 S

Nota:

Teorema 2

L=L(G) I L.I.C.: $ G in FNC a.i. L=L(G).

Ideea demonstratiei:

Se aplica un fel de tranzitivitate a productiilor

Demonstratie

Fie G = (V,S, P, S), L = L(G); construim G= (V0,S0, P0, S0), echivalenta, in FNC.

Evident: S0= S, dar V0, P0, S0 se vor modifica astfel:

(P1) adaugam un nou simbol de start S0 si

o noua productie: S0 S

=> smb. de start al noii gramatici nu va aparea in m.dr. al nici unei productii,

adica se garanateaza conditia B S C.

(P2) eliminam productiile A l, A S;

apoi, pt fiecare aparitie a simbolul A in membrul drept al unei productii adaugam o productie similara in care simbolul A respectiv a disparut.

exemplul 1:

Productia R uAvAw, u,v,w I (V S )*, este inlocuita cu:

R uvAw,

R uAvw,

R uvw,

exemplul 2:

Productia R uAv, u,v I (V S )*, este inlocuita cu:

R uv

exemplul 3:

Productia R A este inlocuita cu:

R l (doar daca R l nu a fost deja eliminata).

(P3) inlocuim perechile de productii unitare de tipul:

A B,

B u, uI(V S )*,

cu A u,

B u,

doar daca A u nu este o regula unitara care a fost deja eliminata.

(P4) pentru productiile duble de tipul:

A u1u2, unde ui IV sau ui I S, i=1,2

  • se inlocuieste fiecare terminal ui cu neterminalul Ui si
  • se adauga o noua productie Ui ui, i=1,2

Nota:

(P3) inlocuim perechile de productii unitare:

pt ca pe cele unitare singulare le-am tratat la pasul 2

Atentie: u este o secventa de terminale si neterminale, nu un singur simbol!!!!!

(P5) restul productiilor, adica cele de tipul:

A u1u2u3un, n ≥ 3 si ' 1in: ui IV sau ui I S,

se inlocuiesc, fiecare, cu setul de productii

A u1A1,

A1 u2A2,

A2 u3A3,

..

An-2 un-1un,

unde A1, A2, ,An-2 sunt noi variabile, adaugate lui V0. q.e.d.

Lema de pompare pentru L.I.C.

Fie A S*, AIL.I.C. =>

$ pIN (constanta=lungimea de pompare) a.i.

'sIA, |s| ≥ p $ u,v,x,y,zIS* cu proprietatile:

(i) s = uvxyz,

(ii) 'i ≥ o: uvixyiz I A,

(iii) |vy| > 0,

(iv) |vxy| p.

Nota:

Ca si in cazul limbajelor regulate, lema de pompare pt LIC este utilizata pentru a demonstra ca un limbaj L nu este independent de context.

Lema de pompare pentru L.I.C.

Ideea demonstratiei:

Consideram arborele de derivare al unei secvente sIA f. lunga => arborele de derivare e f. adanc. =>

=> $ cel putin un terminal care apare in s si care eticheteaza o frunza din arborele de derivare al s si pentru care drumul care il leaga de radacina este f. lung. =>

=> pe acest drum $ cel putin un neterminal X care se repeta ca eticheta de nod =>

putem inlocui subarborele care are ca radacina a 2a aparitie a lui X cu subarborele care are ca radacina prima aparitie a lui X (mai lung) si obtinem tot un arbore de derivare valid pentru G =>

=>obtinem tot o fraza din A

demonstratie

Constanta de pompare:

p = ncard(V)+2, unde n=|w|, ' Aw I P.

Putem pp. ca n ≥ 2.

i=2 i=0

Definitii 6

'L1,L2S*:

L1L2=,

L1L2=,

L1 L2=,

L1 o L2=,

mi(L)=.

 

Lema 3

L.I.C. este inchisa la reuniune, concatenare si operatia *.

demonstratie

Fie L1,L2IL.I.C, Li=L(Gi), unde Gi=(Vi,Si,Pi,Si), ' i=1,2:

L1L2 este generat de G=(V,S,P,S), unde:

V=V1 V2 ,

S= S1 S2,

S=S0,

P=P1 P2 .

L1 o L2 este generat de G=(V,S,P,S), unde:

V=V1 V2 ,

S= S1 S2,

S=S0,

P=P1 P2 .

L* este generat de G=(V,S,P,S), unde:

V=V ,

S= S,

S=simbolul de start,

P=P .

Evident, toate cele 3 garamatici sunt independente de context.

Lema 4

L.I.C. este inchisa la operatia mirror si la omomorfism.

demonstratie

(i) Fie LIL.I.C, L=L(G), unde G=(V,S,P,S); putem pp ca G este in FNC

=> construim G=(V,S,P,S), unde

P= .

L(G)=mi(L), i.e. : SG =>* w S G=>* mi(w), adica:

S=>x1=>x2=>=>xn este o derivare in G

S=>mi(x1)=>mi(x2)=>=>mi(xn) este o derivare in G.

n=1

=> x= l sau x I S => evident.

n≥1

Fie SG =>* x, respectiv S G=>* mi(x) in n+1 pasi =>

1) Prima productie este SAB, respectiv SBA

2) $ yIS* a.i. x=yB => mi(x)=mi(yB)=Bmi(y)

=> lg derivarii lui y in G (mi(y) in G) este n

cf. ip.ind.

$ o derivare pt y in G iff $ o derivare pt mi(y) in G.

compunere cu SAB (SBA)

$ SG =>* x S G=>* mi(x).

(ii) Inchiderea la [substitutie] si omomorfism se dem. analog.

Lema 5

L.I.C. NU este inchisa la intersectie si complementara.

demonstratie

(i) Fie G1=(,,,S},

G2=(,,,S}.

=> L(G1)= I L.I.C;

L(G2)= I L.I.C.

Observam ca L(G1)L(G2)= L.I.C.

(ii) Ppa L.I.C. inchisa la complementara si fie LIL.I.C. =>


Cum LIC - inchisa la reuniune si complementara(Lema3si pp noastra de mai sus)inseamna ca L1 L2 I LIC

=> L1L2IL.I.C T L.I.C. inchisa la T contradictie cu (i).

APD reprezinta un nou model de calculabilitate

Stiva

AFN:

APD:

Nota:

APD reprezinta

        un nou model de calculabilitate

        puterea generativa similara G.I.C.

$       $ limbaje pt care caracterul de LIC poate fi mai usor demosntratat cu APD decat cu GIC.

Un APD seamana cu un AFN dar dispune de o componenta suplimentara: o STIVA.

Stiva ofera un spatiu de memorie suplimentar , potential nelimitat, pe langa cel finit al automatului: APD poate scrie (depune) smb. in stiva si le poate citi ulterior.

Obs. Accesul este insa secvential: APD poate citi doar smb. din varful stivei. Chiar si asa, el poate recunoaste limbaje nereg. precum :

$       citeste primul smb. de pe banda de intrare; pp. ca este 0;

$       APD depune acest smb. in stiva;

$       pp. ca si urmatoarele n smb. sunt 0 => APD le depune in stiva ca si pe primul;

$       pp. ca al n+2lea smb. citit este 1 => APD elimina un smb. 0 din stiva;

$       pp. ca si urmatoarele smb. citite de pe banda de intrare sunt 1 => APD elimina cate un smb. 0 din stiva pt fiecare smb. 1 citit;

$       daca la finalul citirii benzii de intrare stiva este vida inseamna ca nr total de smb 1 citite a fost egal cu nr total de smb o citite si depuse in stiva => secventa de intrare face parte din limbaj.

Observatii

AFD AFN

APDN ≥ APD

: APDN, APD;

*}: APDN.

Nota:

Observatii

Din descrirea de mai sus se vede ca APD are intrinsec o natura nedeterminista.

APD poate fi det. sau nedet. Dar in timp ce AFNAFD, APDN au o putere generativa mai mare decat APD:

Exemplu: limbajul poate fi recunoscut si de un APDN si de un APD,

dar limbajul *} nu poate fi recunoscut decat de un APDN.

Deosebiri intre APD si AFD:

1) Doua alfabete, S si G

2) dom(d) = Q x (S) x (G)

3) codom(d) = P(Q x (G).

Nota:

Deosebiri intre APD si AFD:

La APD trebuie sa luam in considerare nu numai banda de I si setul de stari ci si stiva;

simbolurile scrise in stiva pot fi preluate din acelasi alfabet / din alt alfabet decat cel al benzii de intrare => in definitia APD vom avea 2 alfabete: S si G.

Urmatoarea actiune a APD este det. de:

        starea crt. a APD,

        simbolul citit de pe banda de intrare

        simbolul aflat in varful stivei,

        atentie: APD poate intalni si pe banda de intrare si in stiva smb. vid, l. =>

Dom. de def. al functiei de trazitie d este Q x (S) x (G).

Urmatoarea actiune a APD poate consta in:

trecerea intr-o noua stare si EVENTUAL scrierea unui smb, in stiva.

In plus, modelul APD fiind intrinsec nedeterminist, APD poate trece in diferite stari=>codom(d)=P(Q x (G).

Definitia 7

Automat pushdown=APD=(Q, S, G, d, q0, F), unde:

Q = multime finita, nevida, ale carei elemente se numesc stari;

S = multime finita, nevida, numita alfabet de intrare, ale carei elemente se numesc simboluri, (Sl = S);

G= multime finita, nevida, numita alfabetul stivei, (Gl = G);

d : Q x Sl x Gl P(Q x Gl), numita functia de tranzitie;

q0 IQ, numita starea initiala;

FQ numita multimea starilor finale.

Notatie

Observatie

  • Metoda standard de testare a vidarii stivei: $ I G;
  • Metoda standard de testare a terminarii secventei de intrare: trecerea intr-o stare finala.

Teorema 3

Fie L S*. Atunci:

$ G I G.I.C.: L=L(G) $ A I APD: L=L(A).

Nota:

Notatie

APD, aflat in starea qi,

        citeste smb. a de pe banda de intrare,

        extrage smb. b din stiva,

        depune smb. c in stiva.

Daca a = l T APD face tranzitia (chiar daca/si) fara sa citeasca nimic de pe banda de intrare;

Daca b = l T APD face tranzitia (chiar daca/si) fara sa extraga nimic din stiva;

Daca c = l T APD face tranzitia (chiar daca/si) fara sa depuna nimic din stiva.

Observatie

       Definitia formala a APD NU contine nici un mecanism explicit de testare a vidarii stivei T

METODA STANDARD: se utilizeaza un smb. special din G, $, care este depus in stiva de la inceput;

cand acest smb. este intalnit (cand a ajuns in varful stivei) inseamna ca stiva s-a golit.

       Analog, definitia formala a APD NU contine nici un mecanism explicit de testare a terminarii secventei de intrare T

METODA STANDARD: trecerea intr-o stare finala numai cand s-a incheiat citirea tuturor smb. de pe banda de intrare.

Teorema 3

Echivalenta dintre GIC si APD ca putere generativa

Fie L S*. Atunci:

$ G I G.I.C.: L=L(G) $ A I APD: L=L(A).

CURS 3

Masini Turing

1. Exemple

2. Definitia formala

3. Limbaje Turing-recunoscute si limbaje Turing-decidabile

Nota:

TM reprezinta un model de calcul mult mai puternic decat

        AFD sau AFN (memorie finita) sau

        APD (memorie infinita dar accesibila doar secvential).

Masina Turing (TM) a fost definita de matematicianul englez Alan TURING in 1936 ca un dispozitiv de calcul menit sa calculeze orice functie intuitiv calculabila. In acest scop, A.Turing a inzestrat masina cu o memorie infinita si fara restrictii de acces si cu un dispozitiv de citire/scriere.

=> o MT poate face tot ce poate face un calculator real.

Totusi exista probleme pe care nicio MT (si nici un calculator real) nu le pot rezolva.

Aceste probleme transcend limitele teoretice ale calculabilitatii.

Nota:

1) Informal: O TM este un automat care dispune de:

        O banda infinita, utilizata ca dispozitiv de memorare => o TM are memorie infinita;

        Un cap de citire/scriere care se poate deplasa pe banda,

poate citi / scrie simboluri pe banda.

Initial, banda contine numai secventa de intrare si e vida in rest. Daca masina trebuie sa memoreze informatii, ea poate scrie aceste info. Pe banda. Si aceasta info. poate fi citita prin deplasarea capului de citire/scriere la stanga (inapoi) pe banda.

2) Masina calculeaza astfel:

Citeste un smb. de pe banda si se muta dintr-o stare in alta pana poate produce un rezultat. Aceasta revine la trecerea intr-o stare de acceptare sau de respingere, corespunzator acceptarii / respingerii secventei de intrare. Daca TM nu intra nici in starea de accepatre nici in starea de respingere, atunci, pe secventa respectiva de intrare, va cicla la infinit.

MT poate sa simuleze

  • orice calculator real
  • orice limbaj de programare.

Nota:

1) Care este deci relatia unei MT cu un calculator real?

Un calculator dispune de o memorie cu acces direct, in timp ce

memoria unei MT (banda ei de lucru) este scanata intotdeauna secvential (nu este permis nici un fel de salt). Prin scanari repetate si marcarea simbolurilor prelucrate, putem simula insa accesul direct la simbolurile de pe banda MT.

2) O MT poate fi privita si ca un limbaj de programare (foarte slab si primitiv dar capabil totusi sa programeze orice algoritm):

        dispune de o structura de date (unica): stringul;

        dispune de un set redus de instructiuni (de calcul si de test):

       deplasarea cursorului la dreapta;

       deplasarea cursorului la stanga;

       citirea simbolului din celula curenta;

       scrierea unui simbol peste simbolul din celula curenta;

       alegerea uneia dintre operatiile de mai sus in functie de simbolul citit in celula curenta;

Exista variante de MT (numite enumeratoare) care, pe langa banda de intrare, dispun si de o imprimanta ca dispozitiv de iesire.

Exemplu

Fie L = *}. Construim o MT care sa testeze apartenenta unei secvente binare la L.

idee:

avem voie sa ne deplasam la stanga si la dreapta in secventa de intrare si putem marca un simbol, odata ce l-am examinat.

Cursorul va scana in mod repetat secventa de intrare:

  • la fiecare trecere va compara un simbol din stanga cu unul situat in dreapta lui # si, daca coincid, le inlocuieste cu x;
  • daca toate simbolurile din secventa au fost inlocuite cu x, atunci MT trece in una dintre starile finale de acceptare; altfel trece in una dintre starile finale de respingere.

Nota:

Idee: ca la AFD, ne plasam in postura unei MT: citim o secv. kilometrica de smb si tb sa verificam daca ea consta din 2 subsecvente identice separate printr-un smb special.

Secventa e prea lunga pt a o putea tine minte intergal, dar avem voie sa ne deplasam la stg. si la dr. ei si, de asemenea, putem marca un smb odata ce l-am examinat.

=> algoritmul:

(P1) se scaneaza secventa de intrare wI* in cautarea simbolului special # ;

daca simbolul este gasit, atunci se trece la pasul 2; altfel, secventa este respinsa.

(P2) se scaneaza prima pereche de simboluri cele mai din stanga din cele 2 subsecvente;

daca coincid, atunci se inlocuiesc cu x si se trece la pasul 3; altfel, secventa este respinsa.

(P3) se scaneaza urmatoarea pereche de simboluri, pana se epuizeaza simbolurile din stanga lui #;

daca la dreapta lui # mai raman simboluri binare, atunci secventa de intrare w este respinsa; altfel, w este acceptata.

Definitia formala

Definitia 1

MT = un sistem (Q, S, G, d, q0, qa, qr) unde:

Q = multime finita: multimea starilor;

S = multime finita: alfabetul de intrare; SQ=;

G = multime finita: alfabetul benzii; SG, VIG, VS ;

d : Q x G Q x G x : functia de tranzitie;

q0 I Q: starea initiala;

qa I Q: starea finala de acceptare a secventei de intrare;

qr I Q: starea finala de respingere a secventei de intrare.

Notatie

MT =

Observatie: Modul de calcul al MT:

1) Initial, MT se afla in starea q0

si primeste pe banda, in primele n locatii din extr. stg., secventa de intrare w=w1w2wnIS*.

(restul benzii este vida: locatiile sunt umplute cu simbolul blank ┴). Cum S nu contine smb. blank, primul blank ┴ care apare pe banda marcheaza sfarsitul secv. de intrare.

2) Cursorul se afla in extremitatea stanga a benzii (in prima locatie). Dupa lansarea MT in lucru, aceasta calculeaza cf. definitiei fctiei de tranzitie:

d(q,a)= (p,b,R)

MT, aflata in starea q, citeste pe banda de intrare simbolul a =>

  • MT trece in starea p,
  • inlocuieste simbolul a cu simbolul b in celula examinata si
  • deplaseaza cursorul cu o celula la dreapta celulei examinate.

3) Daca MT incearca sa deplaseze cursorul dincolo de extremitatea stanga a benzii, acesta ramane in dreptul primei locatii din extremitatea stanga, chiar daca fctia de tranzitie indica prin smb L - o deplasare la stg.

4) Calculul continua pana MT ajunge in qa sau qr si se opreste. Altfel, cicleaza nedefinit.

Definitia 2

Configuratie a unei MIMT = un triplet format din:

  • starea curenta a M, q;
  • continutul curent al benzii, v w;
  • pozitia curenta a cursorului.

Notatie

vqw, v,wIG*, qIQ.

Exemplu

Configuratia 1011q701111 inseamna:

Nota:

Am vazut ca, pe masura de MT calculeaza secv. de intrare, apar modificari ale:

        starii crt. a MT,

        continutului benzii,

        pozitiei cursorului (indicata de primul simbol din w).

Un triplet de astfel de valori se n. configuratie a MT.

Definitia 3

Configuratia C1 produce configuratia C2

MT trece corect din C1 in C2 intr-un singur pas

Fie a,b,c I G,

v,w I G*,

qi, qj I Q

Spunem ca o configuratie vaqibw produce configuratia vqjacw daca d(qi,b)=(qj,c,L);

Analog: o configuratie vaqibw produce configuratia vacqjw daca d(qi,b)=(qj,c,R).

Cazuri particulare de configuratii:

1) Configuratia initiala: q0w (MT este in starea initala si cursorul este in dreptul primului smb din secv. de intrare w);

2) Configuratii de oprire = nu produc o alta noua configuratie

  • configuratia de acceptare : q=qa, (= orice configuratie in care q=qa;)
  • configuratia de respingere : q=qr; (= orice configuratie in care q=qr;)

3) Cursorul este in extr. stanga a benzii => config. curenta qibw produce:

  • qjcw daca cursorul ramane pe loc, (evitam deplasarea lui dincole de extr. stg. a benzii);
  • cqjw daca cursorul se deplaseaza la dreapta;

4) Cursorul este in extr. dreapta a benzii =>

config. curenta vaqi este echivalenta cu vaqi┴ . => am redus acest caz part. la cazul general cu ┴ in loc de bw.

Limbaje Turing-recunoscute si limbaje Turing-decidabile

Definitia 4

MIMT M accepta secventa de intrare w IS*

$ o secventa de configuratii C1, C2, , Cs astfel incat:

1)     C1 este configuratia initiala a lui M pentru intrarea w,

2)     ' 1is-1: Ci Ci+1 ,

3)     Cs este o configuratie de acceptare.

Definitia 5

Fie MIMT: L(M) = limbajul masinii Turing M = .

Nota:

L(M) = limbajul masinii Turing M = multimea frazelor peste S acceptate de M.

Definitia 6

Limbajul LS* se numeste Turing-recunoscut = recursiv enumerabil

$ MIMT: L=L(M).

Definitia 7

1) MIMT se numeste decidenta M se opreste indiferent ce secventa primeste la intrare.

2) Fie MIMT si LS*; Spunem ca M decide asupra limbajului L

(i) L=L(M),

(ii) M este decidenta.

Nota:

O MT poate esua asupra unei secv. de intrare daca:

1)     Intra in starea qr si deci respinge secventa;

2) Intra intr-o ciclare infinita (ceea ce nu inseamna neaparat repetarea aceleasi secv. de pasi ci o comportare mai mult sau mai putin complexa care insa nu duce niciodata in una dintre starile finale qa sau qr.

=> Pot aparea situatii in care MT calculeaza un timp indelungat fara a produce niciun rezultat si totusi NU SE POATE DECIDE daca acest fapt se indica

T    intrarea in ciclare sau pur si simplu

T    un calcul f. complicat care cere f. mult timp.

=> E preferabil sa lucram cu MT care, pt. ' secv. de intrare, se opresc (nu cicleaza niciodata). Astfel de MT se n. decidente.

Definitia 8

Limbajul LS* se numeste [Turing-]decidabil = recursiv

$ MIMT decidenta: L=L(M).

Nota:

Adica: L este recunoscut de o MT care se opreste indiferent de secventa primita la intrare.

Observatie

' L Turing-decidabil => L este Turing-recunoscut dar

(rec.) (r.e.)

<

Nota:

$ L Turing-recunoscute care nu sunt Turing-decidabile

Exemplul 1

L1 = {wI* | $nIN: |w|=2n+1} este Turing-decidabil =>

M1=Fie secventa de intrare wI*:

  1. Daca pe banda de intrare $! simbol, atunci M1 accepta; altfel, se aduce cursorul in extremitatea stanga a benzii.
  2. Se scaneaza banda si se bareaza primul simbol intalnit (nemarcat).

Daca nu exista, atunci M1 respinge.

  1. Se scaneaza banda si se bareaza primul simbol intalnit (nemarcat).

Daca nu exista, atunci M1 accepta; altfel, se aduce cursorul in extremitatea stanga si se reia de la Pasul 2.

Definim formal M1=(, S=, G=, d, q0, qa, qr)

unde d:

Exemplu de secventa acceptata de M1:

q0101 = q0101┴ 1q101┴ 10q01┴ 101q1 101qa

Exemplu de secventa respinsa de M1:

q01011 = q01011┴ 1q1011┴ 10q011┴ 101q11┴ 1011q0 1011qr.

Exemplul 2

L2 = este Turing-decidabil =>

M2=Fie secventa de intrare wI*:

  1. Se scaneaza banda de la stanga la dreapta;

daca se intalneste un simbol diferit de 0, atunci M2 respinge.

2. Se aduce cursorul in extremitatea stanga si se scaneaza banda, barandu-se simbolurile 0 din 2 in 2, incepand cu primul 0 nebarat intalnit.

3. Daca la Pasul 2 banda continea un singur simbol 0, atunci M2 accepta.

4. Daca la Pasul 2 banda continea mai mult de un simbol 0 si numarul de simboluri 0 era impar, atunci M2 respinge.

5. Se readuce cursorul in extremitatea stanga a benzii.

6. Se reia Pasul 2.

Definim formal

M2=(,

S=, G=, d, q1, qa, qr),

Nota:

Explicam codificarea folosita:

        Eticheta 0 ,R de pe tranzitia de la q1 la q2 inseamna ca MT aflata in starea q1 citeste de pe banda smb. 0;

ca urmare, MT trece in starea q2, depune smb blank in celula citita si deplaseaza cursorul catre dreapta,

adica: sageata, cele 2 stari pe care aceasta le leaga si eticheta sagetii corespund tranzitiei: d(q1,0)= (q2,┴,R).

        Eticheta 0 R de pe tranzitia de la q3 la q4 inseamna ca MT aflata in starea q3 citeste de pe banda smb. 0;

ca urmare, MT trece in starea q4, nu modifica insa continutul celulei (benzii) si deplaseaza cursorul catre dreapta,

adica: sageata, cele 2 stari pe care aceasta le leaga si eticheta sagetii corespund tranzitiei: d(q3,0)= (q4,0,R).

Modul de lucru al M2:

Ea incepe prin a depune un blank peste cel mai din stanga 0 de pe banda => Mt va putea determina, la Pasul 5, extr. stg. a benzii (puteam folosi ca delimitator stanga un smb special, ca de ex. #, dar am fi marit alfabetul G si am fi complicat diagrama.

Exemplu de secventa acceptata de M2:

q10000 ┴q2000 ┴xq300 ┴x0q40 ┴x0xq3 ┴x0q5x┴ ┴xq50x┴ ┴q5x0x┴ q5┴x0x┴ ┴q2x0x ┴ ┴xq20x ┴

0000

┴xxq3x┴ ┴xxxq3 ┴xxq5x┴ ┴xq5xx┴ ┴q5xxx┴ q5 xxx┴ ┴q2xxx┴ ┴xq2xx┴

┴xxq2x┴ ┴xxxq2 ┴xxx┴qa

Observatie

Testul din Pasul 4 al MT M2 se poate efectua si prin apelarea MT M1.

Nota:

=> diagrama de stare trebuie modificata corespunzator.

Observam ca MT pot modela si capacitatea calculatoarelor reale de a rula programe care apeleaza alte programe.

Exercitii

MT pentru limbajele:

L3 = { w#w | w I* };

L4 = ;

L5 = { #x1#x2##xn| xiI* si xixj, '1ij n, nIN }.

CURS 4

Variante de masini Turing

  1. Terminologia de descriere a MT
  2. MT cu 3 deplasari
  3. MT cu mai multe benzi
  4. MT nedeterministe
  5. Enumeratoare
  6. Echivalenta modelelor de calculabilitate
  7. Problema a 10-a a lui Hilbert

Terminologia de descriere a MT

O MT poate fi descrisa in 3 moduri:

  • formal:

sunt date complet Q, S, G, d;

  • la nivelul implementarii MT:

se utilizeaza limba naturala pt a defini:

     modul in care se deplaseaza cursorul,

     modul de memorare a informatiei de pe banda de lucru;

  • la nivelul cel mai inalt:

se utilizeaza limba naturala pt a descrie un algoritm, ignorand complet modul de implementare a acestuia.

Definim formatul si notatia utilizate pt a descrie o MT:

datele de intrare constau intotdeauna dintr-o secventa de simboluri;

daca intrarea trebuie sa fie un obiect (un graf, un polinom, un automat etc. sau o combinatie a acestora), atunci va trebui mai intai sa-l reprezentam printr-o secventa.

Intrucat codificarile alternative pot fi decodifcate unele in altele de catre MT (eficient) => putem alege orice codificare pt obiectul de intrare.

Vom nota

  • 1! obiect O, codificat printr-o secventa, prin <O>;
  • mai multe obiecte O1,O2,..,On, codificate printr-o unica secventa, prin < O1,O2,..,On >.
  • prima linie a textului va descrie datele de intrare ale MT;
  • daca intrarea este:
  • chiar o secventa de simboluri w => ea este interpretata ca un cuvant peste un alfabet si notata w;
  • codificarea unui obiect <A> => MT incepe automat cu VERIFICAREA CORECTITUDINII CODIFICARII.
  • algoritmul este impartit in etape pasi de calcul numerotati;
  • bloc indentare.

Problema:

Sa se gaseasca un algoritm care sa verifice daca un graf neorientat oarecare este conex sau nu.

Formalizare:

Fie A = un limbaj care consta din toate secventele care reprezinta grafuri neorientate conexe =>

A = ;

trebuie sa gasim o MT decidenta care sa decida asupra limbajului A.

M = Fie intrarea <G> (adica: o codificare a grafului G):

1. Se selecteaza primul nod din G si se marcheaza.

2. Se reia pasul urmator pana cand nu se mai pot marca noi noduri:

3. Fie un nod oarecare v din G; daca el este legat printr-o muchie de un nod deja marcat, atunci nodul v trebuie marcat si el.

4. Se scaneaza toate nodurile din G pt a verifica daca sunt toate marcate sau nu. Daca sunt marcate toate nodurile, atunci M accepta; altfel, M respinge.

Exemplu

<G>=((1,2,3,4);(1,2),(1,3),(1,4),(2,3)).

Explicam modul de codificare a lui G:

MT incepe prin a verifica corectitudinea codificarii <G>.

Daca testul se incheie cu succes (codificarea e corecta), atunci MT trece la prima etapa a algoritmului.

MT cu 3 deplasari

Exemplu

Fie MT = (Q, S, G, d, q0, qa, qr) unde:

d : Q x G Q x G x ;

Fie MT = (Q, S, G, d, q0, qa, qr) unde:

d : Q x G Q x G x ;

d(qi, a) = (qj,b,S)

d (qi, a) = (qk,b,R), d (qk, b) = (qj,b,L).

=> Cele 2 modele sunt computational echivalente dar:

  • e nevoie de cate o o stare auxiliara suplimentara;
  • sunt necesare 2 tranzitii in loc de una.

Nota:

Vom arata ca MT este un model de calculabilitate ROBUST,

i.e.: MT standard, cu n benzi, nedet, recunosc aceeasi clasa de limbaje.

(si AFD si APD sunt destul de robuste dar nu la fel de robuste ca MT!!!)

Exemplu

Fie MT = (Q, S, G, d, q0, qa, qr) unde:

d : Q x G Q x G x ;

Fie MT = (Q, S, G, d, q0, qa, qr) unde:

d : Q x G Q x G x ;

Adica: cursorul se poate deplasa la stg/dr. sau poate ramane pe loc.

MT si MT recunosc aceeasi clasa de limbaje pt ca fiecare tranzitie a MT de forma

d(qi, a) = (qj,b,S)

poate fi simulata prin 2 tranzitii de forma:

d (qi, a) = (qk,b,R), d (qk, b) = (qj,b,L)

=> Cele 2 modele sunt computational echivalente dar pretul simularii MT cu 3 deplasari de catre o MT cu 2 deplasari este:

        spatiu de memorie mai mare (e nevoie de cate o stare auxiliara suplimentara);

        timp de executie mai lung (e nevoie de 2 tranzitii in loc de una).

In continuare, vom da pentru MT doar descrierea la nivelul cel mai inalt; din ea se poate deriva relativ usor functia de tranzitie.

MT cu mai multe benzi

Definitia 1

O MT cu mai multe benzi este o MT standard

M = (Q, S, G, d, q0, qa, qr) care:

    (i)          are n1 benzi de lucru si n1 cursoare corespunzatoare;

  (ii)          initial prima banda contine secventa de intrare iar celelalte n-1 benzi sunt vide;

(iii)          d : Q x Gn Q x Gn x n,

d(qi,a1,a2,,an) = (qj,b1,b2,,bn,L,R,S,L,,S).

Nota:

Definitie

O MT cu mai multe benzi este o MT standard

M = (Q, S, G, d, q0, qa, qr) care:

                        (i)          are n1 benzi de lucru si n1 cursoare corespunzatoare;

                      (ii)          initial prima banda contine secventa de intrare iar celelalte n-1 benzi sunt vide;

                    (iii)          Functia de tranzitie este modificata pt a permite cursoarelor sa citeasca, sa scrie si sa se deplaseze pe unele sau pe toate benzile simultan:

d : Q x Gn Q x Gn x n,

d(qi,a1,a2,,an) = (qj,b1,b2,,bn,L,R,S,L,,S);

Adica: MT se afla in starea qi si cursorul k citeste simbolul ak de pe banda k, 1kn. Ca urmare, MT trece in starea qj iar cursorul k scrie pe banda k simbolul bk, 1kn, dupa care se deplaseaza la dr/stg sau ramane pe loc.

Aparent mai puternice, si MT cu mai multe benzi sunt computational echivalente cu MT standard pt ca ' MT cu mai multe benzi poate fi simulata cu o MT standard.

Teorema 1

' M = MT cu mai multe benzi =>

$ S = MT standard a.i. L(S) = L(M).

ideea demonstratiei

Fie M = (Q, S, G, d, q0, qa, qr) o MT cu n2 benzi si

S = (Q, S, G, d, q0, qa, qr) o MT standard.

Nota:

Teorema 1

Pentru orice MT cu mai multe benzi se poate construi o MT standard, echivalenta.

ideea demonstratiei

Fie M = (Q, S, G, d, q0, qa, qr) o MT cu n2 benzi si

S = (Q, S, G, d, q0, qa, qr) o MT cu 1! banda.

Vom simula MT M cu ajutorul MT S memorand info. de pe cele n2 benzi ale M pe banda (unica) a lui S.

Exemplu:

=>

=> (i) un simbol aditional #, pt delimitator;

(ii) ' aIS $ a IG

=> S devine o MT cu mai multe benzi si cursoare virtuale.

Nota:

Exemplu

=> In acest scop am folosit:

(i) un simbol aditional, #, ca delimitator, pentru a separa pe unica banda a lui S, cele n secvente de pe cele n benzi ale M;

(ii) cate un nou simbol pt fiecare simbol din S, pt a simula pozitia cursorului corespunzator (adica: pt fiecare simbol aI G adaugam in G simbolul a )

=> S devine o MT cu mai multe benzi si cursoare virtuale.

demonstratie

S = Fie secventa de intrare w=w1w2wkIS*:

1. S isi formateaza banda de intrare pt a reprezenta cele n benzi ale M, la momentul initial:

#w1w2w3wk#^ #^#..# ^ #^

banda 1

banda 2

banda 3.banda n

2. S scaneaza unica sa banda de la primul delimitator # pana la cel de-al (n+1)lea delimitator # in scopul de a determina simbolurile aflate in dreptul cursoarelor virtuale.

Apoi, S mai face o parcurgere pentru a actualiza benzile virtuale conform definitiei functiei de tranzitie a lui M;

3. Daca S deplaseaza unul dintre cursoarele virtuale la dreapta unui delimitator #, aceasta inseamna ca M a mutat cursorul corespunzator peste portiunea vida a benzii respective. => S:

    • depune simbolul special ^ in celula respectiva de pe unica sa banda,
    • deplaseaza continutul benzii sale, de la acea celula pana la cel mai din dreapta delimitator #, cu o celula la dreapta.

Apoi, continua simularea ca mai sus.

Corolar 1

'LS* este Turing-recunoscut

$ o MT cu mai multe benzi, M, a.i. L=L(M).

demonstratie

T

' MT standard este o MT cu mai multe benzi triviala (n = 1).

Fie MIMT, M are mai multe benzi: L=L(M);

Cf. Teoremei 1, $ SIMT standard, echivalenta cu M;

T L = L(S).

MT nedeterminsite

  • MTN ≈ AFN, APDN;
  • Modelul de calcul: arbore;
  • MTN accepta secventa de intrare

cel putin una dintre ramurile arborelui are ca eticheta a frunzei o configuratie de acceptare.

Definitia 2

O MT nedeterminista este o MT standard

M = (Q, S, G, d, q0, qa, qr) unde:

d : Q x G P(Q x G x ).

Teorema 2

' N = MT nedeterminista =>

$ S = MT standard a.i. L(S) = L(N).

ideea demonstratiei

Fie N o MT nedeterminsita;

este suficient sa construim o MT, M, cu trei benzi care sa simuleze N deoarece,

conform Teoremei 1, vom putea apoi sa construim o MT standard, S, care sa o simuleze pe M.

  • M va incerca toate ramurile de calcul posibile ale N;
  • daca va ajunge vreodata in starea qa atunci M recunoaste secventa de intrare, altfel simularea nu se va termina.
  • Cautarea unei configuratii de acceptare efectuata de M in arborele lui N:
  1. DEPTH FIRST;
  2. BREADTH FIRST.

cazul (1): exploram in adancime o ramura infinita si ignoram una valida.

cazul (2): sigur vom examina toate nodurile arborelui pana gasim configuratia de acceptare

Nota:

Vom simula MT nedeterminsita N cu o MT determinista cu mai multe benzi M astfel:

        pentru fiecare secventa de intrare primita, M va incerca toate ramurile de calcul posibile ale N;

       daca va ajunge vreodata in starea qa atunci M va recunoaste secventa de intare respectiva, altfel, simularea nu se va termina;

       cautarea efectuata de M in arbore pt a gasi o configuratie de acceptare se poate face DEPTH FIRST sau BREADTH FIRST.

Prima strategie pare mai indicata dar nu este!!!!: putem explora in adancime o ramura de calcul infinita si sa ignoram astfel o ramura valida!!!

=> utilizam metoda BREADTH FIRST: vom vizita toate nodurile de pe nivelul n inainte de a trece la nodurile de pe nivelul n+1;

=> astfel suntem siguri ca vom examina toate nodurile arborelui pana gasim configuratia de acceptare.

demonstratie

Fie d : Q x G P(Q x G x ) functia de tranzitie a lui N.

Notam b=max)=codom(d)}

=> b=nr max de copi pe care ii poate avea un nod din arborele de derivare al lui N

Notam cu Sb=.

Construim o MT determinista M cu 3 benzi astfel:

  • banda 1: contine permanent cuvantul de intrare;
  • banda 2: contine si actualizeaza permanent un duplicat al continutului benzii de lucru a lui N, reprezentand una dintre ramurile de calcul nedeterminist efectuat de N;
  • banda 3: tine evidenta pozitiei din arbore in care se afla S .

banda de intrare

banda de simulare

banda de adresa

Banda 3 contine in orice moment un cuvant aISb* ;

acest cuvant reprezinta:

  • fie una dintre ramurile de calcul nedeterminist efectuat de N, de la radacina pana la nodul a carui adresa este exact a;
  • fie o adresa nevalida

Nota:

Explicitam modul in care este reprezentata informatia pe banda 3:

intrucat fiecare nod din arborele de calcul (derivare) al N poate avea maximum b copi (cf. obs. de mai sus),

vom asocia fiecarui nod din arbore inca o adresa (eticheta), sub forma unui cuvant peste alfabetul Sb =

Astfel,

        adresa nodului-radacina este cuvantul vid, lI Sb*;

        daca un nod are adresa 231 inseamna ca ajungem la nodul respectiv plecand din radacina catre al doilea ei fiu, apoi la al treilea fiu al fiului radacinii (nepot!) si, in fine, la primul fiu al acestuia (stranepot!))

ATENTIE! nu toate cuvinetele peste Sb* pot fi adrese valide de-a lungul unei ramuri de calcul: de ex. simbolul urmator din secventa este un simbol aISb dar nodul-tata are mai putin de a copii.

Pe de alta parte, fiecare simbol dintr-o secventa valida din Sb* va indica urmatoarea alegere care trebuie facuta atunci cand trebuie simulat un pas pe una dintre ramurile calculului nedeterminist efectuat de N.

Prin urmare, banda 3 contine in orice moment un cuvant aISb* ;

acest cuvant reprezinta:

T    fie una dintre ramurile de calcul nedet. efectuat de N, de la radacina pana la nodul a carui adresa este exact a;

T    fie o adresa nevalida (vezi mai sus).

M=Fie secventa de intrare w:

1. Initial, banda 1 contine cuvantul de intrare w , banda 2 este vida iar pe banda 3 se genereaza primul cuvant aISb* .

2. Se copiaza continutul benzii 1 pe banda 2.

3. Se utilizeaza banda 2 pentru a simula una dintre ramurile calcului nedeterminist efectuat de N pe intrarea w.

Inainte de a simula un pas de calcul efectuat de N, M examineaza simbolul urmator de pe banda 3 pt a determina care dintre posibilitatile de continuare oferite de dN trebuie aleasa.

Daca nu mai sunt simboluri pe banda 3, atunci se trece la Pasul 4.

Daca alegerea facuta este nevalida, atunci se trece tot la Pasul 4.

Daca s-a intrat intr-o configuratie de respingere, se merge tot la Pasul 4.

Daca s-a intrat intr-o configuratie de acceptare, M recunoaste intrarea w si se opreste.

4. Se inlocuieste secventa de pe banda 3 cu urmatorul cuvant peste Sb, in ordine lexicografica. Se simuleaza urmatoarea ramura de calcul al N reluand de la Pasul 2.

Corolar 2

'LS* este Turing-recunoscut

$ o MT nedeterminista, N, a.i. L=L(N).

demonstratie

T

' MT standard este o MT nedeterminista triviala.

Fie NIMT, N este nedeterminista: L=L(N);

Cf. Teoremei 2, $ SIMT standard, echivalenta cu N;

T L = L(S).

Definitie 3

O MT nedeterminista se numeste decidenta

'wIS*, toate ramurile ei de calcul se opresc.

Corolar 3

'LS* este decidabil

$ o MT nedeterminista decidenta, N, a.i. L=L(N).

Enumeratoare

Limbajele Turing recunoscute = limbaje recursiv enumerabile

Enumerator

Imprimanta

Modul de lucru:

  • initial: banda de intrare este vida;
  • limbajul enumerat de E: multimea tuturor secventelor de simboluri printate de imprimanta;
  • situatia de ciclare: tiparirea unei liste infinite de cuvinte.

Teorema 3

Fie LS*; L este Turing-recunoscut

$ EIMT a.i. L=L(E).

demonstratie

Fie EIMT a.i. L=L(E).

M= Fie secventa de intrare w:

1. Se ruleaza enumeratorul E pe intrarea w.

De fiecare data cand E printeaza un cuvant, se compara acest cuvant cu secventa w.

2. Daca apare o coincidenta, atunci M accepta.

Evident, M accepta secventele din lista tiparita de E.

T

Fie MIMT a.i. L=L(M).

E= Indiferent care este cuvantul de pe banda de intrare a lui E, acesta este ignorat:

1. Pentru fiecare i=1,2, se repeta urmatorii pasi:

2. M executa i pasi de calcul pentru fiecare cuvant de intrare s1,s2,,siIS*.

3. Daca vreunul dintre cei i pasi de calcul aduce M intr-o configuratie de acceptare, atunci cuvintele corespunzatoare din sirul s1,s2,,si sunt tiparite de imprimanta lui E.

Observatii

  1. Pentru a construi E a fost nevoie se o listare a cuvintelor din S: orice listare (fara repetitii) este acceptabila.
  2. Evident, daca M accepta un cuvant oarecare sIS*, acesta apare la un moment dat in lista tiparita de E. De fapt, el va fi tiparit de o infinitate de ori deoarece M reia calculul de la pasul 1 pt fiecare i, oridecateori lista s1,s2,,si se lungeste cu inca un cuvant.
  3. Procedura de mai sus simuleaza rularea lui M in paralel pe toate cuvintele de intrare posibile:
  4. i=1 s1 1 pas de calcul
  5. i=2 s1 2 pasi de calcul
  6. s2 2 pasi de calcul
  7. i=3 s1 3 pasi de calcul
  8. s2 3 pasi de calcul acceptat
  9. s3 3 pasi de calcul
  10. i=4 s1 4 pasi de calcul acceptat
  11. s2 4 pasi de calcul acceptat
  12. s3 4pasi de calcul
  13. s4 4 pasi de calcul acceptat
  14. ..

Echivalenta modelelor de calculabilitate

Am definit mai multe variante de MT si am demonstrat echivalenta lor .

Exista si alte modele de calculabilitate:

  • functiile l-calculabile: Alonzo CHURCH, Stephen Cole KLEENE,1934;
  • functiile general recursive: Kurt Godel, 1935
  • sistemele (masinile) Post: Emil POST, 1936
  • algoritmii normali Markov: A.A.MARKOV, 1954.

Toate au aceeasi caracteristica: acces nerestrictionat la o memorie nelimitata.

In plus, toate sunt echivalente cu MT (si deci unele cu altele)

=> clasa algoritmilor pe care o descriu este unica si naturala.

vezi si clasa limbajelor de programare.

Problema a 10-a a lui Hilbert

Algoritm: o notiune primara

Problema a 10-a a lui Hilbert

Nota:

Algoritmii au o istorie lunga in matematica (gasirea numerelor prime, a cmmdc etc.) dar notiunea insasi nu a capatat (inca) o definitie matematica precisa, lucru esential pentru rezolvarea unor probleme importante, care au de cele mai multe ori conotatii filosofice.

Se opereaza insa cu notiunea intuitiva de algoritm, se folosesc descrieri, proprietati etc.

Lipsa unei definitii riguroase a avut nu numai urmari dramatice pt posibilitatea de a rezolva o serie de probleme importante dar a avut si conotatii filosofice dintre cele mai semnificative.

Vom ilustra acest fapt prin intermediul unei probleme celebre, problema a 10-a a lui Hilbert.

Congresul International al matematicienilor, 1900, Paris;

Conferinta lui David HILBERT: lista celor 23 probleme

Observatii

  • un proces cu ajutorul caruia, dupa un numar finit de operatii, sa se determine .
  • Hilbert presupunea ca algoritmul exista si trebuie doar descoperit.
  • Lipsa unei definitii formale pentru notiunea de algoritm solutii pentru cazuri particulare ale problemelor dar nu pentru o clasa intreaga.

Nota:

La Congresul International al matematicienilor care a avut loc in anul 1900 la Paris, matematicianul german David HILBERT a tinut o conferinta devenita celebra. In aceasta conferinta, Hilbert a identificat 23 de probleme pe care le-a considerat a fi o provocare adresata matematicienilor secolului XX. Cea de-a 10a problema din lista implica notiunea neformalizata de algoritm:

sa se gaseasca un algoritm care sa verifice daca un polinom in oricate variabile admite o radacina in Z.

Observatii.

David Hilbert nu a folosit termenul de algoritm ci formularea: un proces cu ajutorul caruia, dupa un numar finit de operatii, sa se determine .

Enuntul problemei indica faptul ca Hilbert nu se indoia de existenta unui astfel de algoritm; el considera dificila doar gasirea lui.

Notiunea intuitiva, neformalizata, de algoritm cu care operau matematicienii la inceputul secolului XX le permitea sa gaseasca algoritmi pentru anumite cazuri particulare ale unor probleme dar in niciun caz nu le putea permite sa DEMONSTREZE inexistenta unui algoritm pt rezolvarea unei CLASE de probleme. Pt acest lucru era nevoie de de definitia riguroasa a notiunii de algoritm.

Teza Church-Turing

Problema a 10a a lui Hilbert.

1970, Yuri MATIJASEVIČ, (Martin DAVIS, Hilary PUTNAM, Julia ROBINSON):

nu exista nici un algoritm care sa verifice daca un polinom oarecare are radacini intregi

Problema a 10a a lui Hilbert este nerezolvabila algoritmic.

Nota:

Aceasta definitie a aparut in anul 1936 in lucrarile lui A. Church si A. Turing.

Asa cum am aratat, primul este autorul formalismului notational denumit l-calcul; al doilea al masinilor omonime.

Imediat s-a demonstrat echivalenta celor 2 definitii matematice.

Relatia dintre aceste definitii matematice riguroase si notiunea informala de algoritm este cunoscuta sub numele de teza Church-Turing:

Clasa alg. (fctiilor intuitiv calculabile) coincide cu clasa fctiilor l-calculabile (fctiilor calculabile cu MT).

Aceasta teza a furnizat o definitie pentru notiunea de algoritm suficienta (si necesara) pentru a rezolva Problema a 10a a lui Hilbert. In 1970, Yuri MATIJASEVIČ, bazandu-se pe rezultate anterioare datorate lui Martin DAVIS, Hilary PUTNAM, Julia ROBINSON, arata ca nu exista nici un algoritm care sa verifice daca un polinom oarecare are radacini intregi ( .Problema a 10a alui Hilbert este nerezolvabila algoritmic.)

Fie D =

D este decidabila ?

D este Turingrecunoscuta dar nu este decidabila.

Cazul unar:

Fie D1=.

Construim o MT, M1, care recunoaste D1:

M1 = Fie p1 un polinom oarecare in variabila x:

1. Se evalueaza p1 succesiv pentru x=0, x=1, x=-1, x=2, x=-2, x=3, ,

2. Daca la un moment oarecare se obtine 0, atunci M1 accepta p1.

Cazul general:

putem construi o MT, M, similara care va testa fiecare polinom de intrare p pentru diferite combinatii de valori, in functie de numarul de variabile.

n=2: (x1,x2)I;

n=3: (x1,x2,x3)I.

AFD A accepta w ? <A,w> I ACCAFD?

T a demonstra ca o problema de calculabilitate este rezolvabila algoritmic a demonstra ca un limbaj (asociat) este decidabil.

Teorema 1

Limbajul ACCAFD= este decidabil.

Teorema 2

Limbajul ACCAFN = este decidabil.

Teorema 3

Limbajul ACCREX = este decidabil.

Observatie

T1, T2, T3

AFD AFN REX din punct de vedere al decidabilitatii limbajului recunoscut/generat

Teorema 4

Limbajul VIDAFD = este decidabil.

Teorema 5

Limbajul EQVAFD = este decidabil.

Probleme decidabile in clasa limbajelor independente de context

Teorema 6

Limbajul ACCGIC = este decidabil.

Lema 1

Fie GIGIC in forma normala Chomsky si wIL(G): |w|=n, nIN;

=> orice derivare a lui w in G are 2n-1 pasi.

Observatie

Teorema anterioara: ' GIC, APD: L(GIC)=L(APD).

T toate rezultatele demonstrate pentru gramaticile independente de context au loc si pentru automatele pushdown.

Teorema 7

Limbajul VIDGIC = este decidabil.

Observatie

Limbajul EQVGIC = :

Cf. Teoremei 5, problema egalitatii limbajelor generate de gramatici REGULATE este decidabila

EQVGIC = NU este decidabil.

Teorema 8

Orice limbaj independent de context este decidabil.

CURS 6

Problema opririi

  1. Metoda diagonalizarii
  2. Nedecidabilitatea unui limbaj dat
  3. Un limbaj care nu este Turing-recunoscut

Definitia 1

Multimea A se n. numarabila

A este finita sau

$ f: N A, bijectiva.

Exemple de multimi numarabile

  1. N =
  2. T =
  3. Enumerarea lui Cantor

Multimile N2 si N au aceeasi cardinalitate (1874)

xy

0

1

2

3

4

5

0

0

1

3

6

10

15

1

2

4

7

11

16

22

2

5

8

12

17

23

30

3

9

13

18

24

31

39

4

14

19

25

32

40

49

5

20

26

33

41

50

60

functia J este bijectiva;

inversele ei sunt:

J(x,y) = numarul lui Cantor asociat perechii (x,y);

Tripletul (J,K,L):

J(K(z),L(z))=z;K(J(x,y))=x,L(J(x,y))=y

triplet de functii pereche

Contraexemplu

R

  1. Q = este numarabila

Utilizam tehnica diagonalizarii

Construim o matrice:

=> numarul rational m/n: celula aflata la intersectia liniei m cu coloana n.


eliminam repetitiile =>


=> $ Limbaje care nu sunt decidabile si nici macar Turing recunoscute.

? multimea limbajelor este nenumarabila,

multimea MT este numarabila,

o MT poate recunoaste 1! limbaj.

Propozitia 1

$La*: LL(M), 'MIMT

demonstratie

(i) MT = multimea masinilor Turing este numarabila

Observam ca multimea a* este numarabila, 'a.

'MIMT poate fi codificata peste un alfabet A convenabil ales.

eliminam 'wIA*: w<M>, ' MIMT

obtinem o enumerare a MT.

(ii) multimea B a secventelor binare infinite este nenumarabila

Folosim metoda diagonalizarii

ppa $ f:N B, bijectiva a.i. f(n)=bnIB .

n

f(n)=bn

1

100

2

010

3

110

4

001

b=00111.

n

f(n)=bn

1

10000

2

01000

3

11000

4

00100

5

10100

bf(n), 'nIN :

a na cifra binara din b este:

0, daca a n-a cifra binara din f(n) este 1;

1, daca a n-a cifra binara din f(n) este 0.

=> B este nenumarabila.

(iii) multimea L = este nenumarabila

E suficient sa gasim f: L B, bijectiva.

Fie a*=; 'L lL infinita, unica, definita astfel:

cel de-al i-lea bit din lL este: 1, daca siIL,

0, daca siL.

Exemplu: a=, L=

=> a*=

L=

=> lL= 0 1 0 1 1 0 0 1 1 1 1 0..

=> f: L B: f(L)= lL.

Evident: f = bijectiva.

cf. (ii) B =nenumarabila => L nenumarabila.

Din (i) si (ii) => exista limbaje care nu sunt Turing-recunoscute

Nedecidabilitatea unui limbaj dat

O MT, M, accepta sau nu o anumita secventa de intrare, w?

PROBLEMA ACCEPTABILITATII pt. LIMBAJE RECURSIV ENUMERABILE

PROBLEMA OPRIRII

ACCMT=

Teorema 1

Limbajul ACCMT= nu este decidabil.

Observatia 1

Lb ACCMT este Turing-recunoscut dar nu este Turing-decidabil:

U = Fie secventa de intrare <M,w>, unde MIMT si wIa*:

1. Se simuleaza M pe intrarea w.

2. Daca M accepta w, atunci U accepta <M,w>;

daca M respinge w, atunci U respinge <M,w>.

==> U recunoaste limbajul ACCMT dar nu decide asupra lui:

M cicleaza pe w U cicleaza pe <M,w>.

? M nu se opreste pe w U respinge <M,w>

ACCMT= decidabil

Observatia 2

Problema acceptabilitatii pt MT, ACCMT, se n. si PROBLEMA OPRIRII tocmai datorita acestui fapt.

Observatia 3

U = exemplu de MT universala

O MT oarecare se numeste universala

ea poate simula orice MT, cu conditia sa primeasca la intrare o descriere corecta a acesteia.

Observatia 4

Teorema 1: MT acceptoare sunt mai puternice decat MT decidente.

demonstratie (T1)

Ppa ca limbajul ACCMT este decidabil T

H = Fie secventa de intrare <M,w>, unde M IMT si wIa*:

1. Se simuleaza M pe intrarea w.

2. Daca M accepta w, atunci H se opreste si accepta <M,w>;

daca M nu accepta w, atunci H se opreste si respinge <M,w>.

D apeleaza H pentru a determina ce actiune executa M atunci cand primeste, ca secventa de intrare w , propria sa descriere <M>;

dupa ce D a obtinut aceasta informatie ea executa exact actiunea contrara, i.e.:

D = Fie secventa de intrare <M> , unde MIMT:

1. Se ruleaza H pe secventa de intrare <M,<M>>.

2. Se returneaza rezultatul opus rezultatului returnat de H, adica,

daca H accepta intrarea <M,<M>> (ceea ce se intampla atunci cand M accepta <M>) atunci D respinge;

daca H respinge intrarea <M,<M>> (ceea ce se intampla atunci cand M nu accepta <M>) atunci D accepta <M>.

Dar MT M din secventa de intrare este oarecare: ce se intampla cand D primeste la intrare propria sa descriere <D>?

respinge, daca D accepta <D>.

T D(<D>) =

accepta, daca D nu accepta <D>,

T contradictie

T nici D nici H nu pot exista in realitate

T limbajul ACCMT nu este decidabil.

Fie multimea tuturor masinilor Turing, MT:

<M1>

<M2>

<M3>

<M4>

M1

acc

V

acc

V

M2

acc

acc

acc

acc

M3

V

V

V

V

M4

acc

acc

V

V

acc, daca Mi accepta intrarea <Mj>,

i.e.: celula (i,j)=

V, daca Mi nu accepta intrarea <Mj> (respinge sau cicleaza)

H

<M1>

<M2>

<M3>

<M4>

M1

acc

resp

acc

resp

M2

acc

acc

acc

acc

M3

resp

resp

resp

resp

M4

acc

acc

resp

resp

i.e.: celula (i,j)= rezultatul returnat de H pe intrarea <Mi,<Mj>>.

H

<M1>

<M2>

<M3>

<M4>

<D>

M1

acc

resp

acc

resp

acc

M2

acc

acc

acc

acc

acc

M3

resp

resp

resp

resp

resp

M4

acc

acc

resp

resp

acc

D

resp

resp

acc

acc

???

Un limbaj care nu este Turing-recunoscut

Definitia 2

Limbajul L S* se numeste co-Turing-recunoscut

$ L a*, L = Turing-recunoscut astfel incat L = a* L.

Teorema 2

' L S*: L este decidabil

L este Turing-recunoscut si co-Turing-recunoscut.

demonstratie T

ip: L este decidabil T L este Turing-recunoscut.

dar: L este decidabil T L este decidabil

T L este Turing-recunoscut T L este co-Turing-recunoscut (cf. def.).

ip: L este Turing-recunoscut si co-Turing-recunoscut

T L si L sunt Turing-recunoscute (cf. def.)

T $ M1,M2IMT: L=L(M1), L =L(M2).

Definim MT, M, astfel :

M = Fie cuvantul de intrare w I S*:

1. Se ruleaza M1 si M2 in paralel pe intrarea w.

2. Daca M1 accepta w atunci M accepta w iar daca M2 accepta w atunci M respinge w.

Rularea in paralel a celor doua MT M1 si M2 : inzestrarea lui M cu 2 benzi de lucru.

Simularea se face alternativ: M simuleaza cate un pas al fiecarei masini pana cand una dintre ele se opreste.

M decide asupra limbajului L:

fie un cuvant oarecare w I S* T w I L sau w I L

T fie M1 fie M2 accepta intrarea w.

Dar, conform definitiei sale, M se opreste oridecateori M1 sau M2 accepta cuvantul de intrare primit.

In plus, M accepta toate secventele din L si respinge toate secventele din L

T M decide asupra limbajului L T L este decidabil.

Corolarul 1

Limbajul NU este Turing-recunoscut.

demonstratie

Ppa: limbajul este Turing-recunoscut

Am dem ca limbajul ACCMT este Turing-recunoscut

ACCMT este decidabil (cf. Teorema 2) T contradictie cu Teorema 1.




loading...





.com Copyright © 2017 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
 PROIECT DE LECTIE Clasa: I Matematica - Adunarea si scaderea numerelor naturale de la 0 la 30, fara trecere peste ordin
 Proiect didactic Grupa: mijlocie - Consolidarea mersului in echilibru pe o linie trasata pe sol (30 cm)
 Redresor electronic automat pentru incarcarea bateriilor auto - proiect atestat
 Proiectarea instalatiilor de alimentare ale motoarelor cu aprindere prin scanteie cu carburator

Lucrari de diploma

vezi toate lucrarile de diploma
 Lucrare de diploma - eritrodermia psoriazica
 ACTIUNEA DIPLOMATICA A ROMANIEI LA CONFERINTA DE PACE DE LA PARIS (1946-1947)
 Proiect diploma Finante Banci - REALIZAREA INSPECTIEI FISCALE LA O SOCIETATE COMERCIALA
 Lucrare de diploma managementul firmei diagnosticul si evaluarea firmei

Lucrari licenta

vezi toate lucrarile de licenta
 CONTABILITATEA FINANCIARA TESTE GRILA LICENTA
 LUCRARE DE LICENTA - FACULTATEA DE EDUCATIE FIZICA SI SPORT
 Lucrare de licenta stiintele naturii siecologie - 'surse de poluare a clisurii dunarii
 LUCRARE DE LICENTA - Gestiunea stocurilor de materii prime si materiale

Lucrari doctorat

vezi toate lucrarile de doctorat
 Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
 Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
 LUCRARE DE DOCTORAT ZOOTEHNIE - AMELIORARE - Estimarea valorii economice a caracterelor din obiectivul ameliorarii intr-o linie materna de porcine

Proiecte de atestat

vezi toate proiectele de atestat
 Proiect atestat informatica- Tehnician operator tehnica de calcul - Unitati de Stocare
 LUCRARE DE ATESTAT ELECTRONIST - TEHNICA DE CALCUL - Placa de baza
 ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
 Proiect atestat tehnician in turism - carnaval la venezia




PROIECT ATESTAT INFORMATICA - GESTIONAREA STOCULUI UNEI FARMACII
Cercetarea concurentei
Conceptul de informatie și data
Algoritmi si scheme logice
Programul Metapathy
Arbori binari Similaritate si echivalenta
Analiza si proiectarea sistemelor informatice de gestiune - seminar
Sincronizare prin semnale



loading...

Termeni si conditii
Contact
Creeaza si tu