Računarski fakultet u Beogradu
Teorija algoritama,
jezika i automata
Predavanje 1
Sreda, 6. oktobar, 2010
13-15 časova
1
Teorija algoritama, jezika i
automata
Knjiga uz kurs:
Automata Theory, Languages and Computation,
by Hopcroft, Motwani, and Ullman
3rd edition, Addison Wesley, 2007
Web stranica kursa:
http://www.freewebs.com/nkablar/ta.htm
E-mail adresa kursa:
[email protected]
2
Predavanja:
sreda, 13-15 časova, soba 1, Računarski fakultet
Konsultacije:
ponedeljak, 13-14 časova, Kabinet 3, Računarski
fakultet
Vežbe:
sreda, 15-17 časova, soba 1, Računarski fakultet
3
Ocenjivanje
Domaći radovi: 4x5%=20%
(nakon
Kolokvijum: 2x25 (15)%=50 (30)%
(prve
III, VI, IX, i XII nedelje)
i druge Kolokvijumske nedelje)
Završni ispit: 30 (50)%
(Januarski,
Aprilski, Junski, Julski, Septembarski i Oktobarski ispitni rok)
Semestar traje 15 nedelja, 13 nedelja
predavanja, 2 kolokvijsumske nedelje
4
Sadržaj kursa
Centralni koncepti teorije automata. Konačni automati
(deterministički i nedeterministički konačni automati,
konačni automati sa tranzicijama).
Regularni izrazi i jezici. Svojstva regularnih jezika.
Kontekstno-slobodne gramatike i jezici.
Pritisni automati.
Svojstva kontekstno-slobodnih jezika.
Uvod u Turingove mašine.
Problem nerešljivosti.
Netraktabilni problemi.
Dodatne klase problema.
5
Karakteristike knjige
Web stranica uz knjigu na engleskom
jeziku
Gradiance sistem
6
Visual Automata Simulator
http://www.cs.usfca.edu/~jbovet/vas.html
Za vežbu i kao ideja daljeg razvoja
software-a.
7
Uvod
8
U čemu su kompjuteri dobri?
1997, IBM Deep Blue je
pobedio svetskog
šampiona u šahu Gari
Kasparova u šest partija.
3½
2½
9
Search... “automata theory”
ta da
a
t
l
u
rez
0
0
0
,
či
8
4
e
r
6
e
o
j
Ok
ivan y”
ž
a
r
t
r
na po ata theo
m
“auto
je
Pretraživač Google
indeksira 2,000,000,000
web stranica. Tu se može
naći mnogo toga
zanimljivog o zadatoj temi.
10
Knjige, mogućnosti...
Preporučene
knjige
Kretanje
letelice
Da li postoji nešto što kompjuteri ne mogu
da urade?
11
Nemogućnosti
Zašto brinemo o onome što je
nemoguće?
12
Perpetualno kretanje
U srednjem veku, ljudi su želeli
mašinu koja ne koristi energiju
Kasnije, otkrića u fizici su pokazala
da se energija ne može stvoriti od
vazduha
Perpetualno kretanje je futile
endeavor (srb. beskorisan pokušaj)
Razumevanje nemogućeg nam pomaže da
kanališemo energije ka onome što je
korisnije.
13
Zakoni izračunavanja
Kao što nam zakoni fizike govore šta
je (ne)moguće za prirodu da uradi...
... zakoni izračunavanja nam govore
šta je (ne)moguće za kompjutere.
14
Teorija automata
Teorija automata proučava zakone
izračunavanja.
U realnosti, zakoni izračunavanja nisu savim
razumeveni, ali teorija automata je dobar početak.
15
Uvod
Teorija automata: studija o abstraktnim uredjajima (eng.
computational devices), tzv. “mašinama”
Istorijski pregled
1930-tih: Turing proučava abstraktne mašine sa ciljem
da precizno opiše granice izmedju onoga šta uredjaj za
izračunavanje može izračunati, a šta ne; njegov
zaključak je primenljiv kako na Turingove mašine tako i
današnje realne računare
1940-tih i 1950-tih: današnji “konačni automati” se
proučavaju od velikog broja istraživača. Originalno su
predloženi da modeliraju funkcije mozga; ispostavili su
se korisnim u veoma različite svrhe. Veliki deo rezultata
tog istraživanja se danas proučava u teoriji automata.
16
Uvod
1950-tih: lingvista Chomsky započinje studiju “formalnih”
gramatika, koje imaju bliske veze sa današnjim
abstraktnim automatima.
1969-te: S. Cook proširuje Turing-ovu studiju onoga što
se može i ne može izračunati. Razgraničio je probleme
koji se mogu efikasno rešiti pomoću računara od onih
problema koji se u principu mogu rešiti, ali u praksi
uzimaju toliko mnogo vremena da su kompjuteri
beskorisni sem za mali broj problema; to vodi ka tzv.
“netraktabilnim” (eng. intractable) problemima, ili tzv. NPteškim (eng. NP-hard) problemima.
17
Uvod
Nasledjeni koncepti se danas koriste
Svi ovi rezultati su doveli do onoga čime se današnji eng. computer
scientists bave danas
Neki od koncepata, kao što su konačni automati i odredjene vrste
formalnih gramatika koriste se u projektovanju raznih vrsta softwarea.
Drugi koncepti, kao što su Turing-ove mašine nam pomažu da
razumemo šta možemo očekivati od našeg software-a. Specijalno,
teorija netraktabilnih problema nam omogućava da zaključimo da li
ćemo biti u mogućnosti da se suočimo sa problemom i napišemo
program koji ga rešava (jer nije u traktabilnoj klasi) ili da li treba da
pronadjemo način da zaobidjemo netraktabilan problem: pronaći
aproksimaciju, koristiti heuristiku i sl.
18
Uvod
U ovom uvodu dajemo viši aspekt shvatanja teorije
automata i njenih primena
U Poglavlju 1 dat je veoma lep pregled tehnika
dokazivanje – fundamentalno za praćenje ovog kursa.
Predjeni su: deduktivni dokazi, reformulisanje izjava,
dokazi kontradikcijom, dokazi indukcijom, i drugi važni
koncepti dokazivanja.
Poslednja sekcija u Poglavlju 1 uvodi koncepte kojima
obiluje teorija automata: azbuku, stringove, i jezik, što
ćemo raditi nešto kasnije.
19
Zašto proučavati teoriju automata?
Postoji nekoliko razloga zašto je teorija
automata i složenosti važan osnov
kompjuterskih nauka i nadalje dajemo osnovnu
motivaciju i naglašavamo oblasti koje će biti
pokrivene na kursu.
20
Uvod u konačne automate
Konačni automati se koriste kao model za
mnoge važne vrste hardware-a i software-a.
Nekoliko primera od značaja:
Software
za projektovanje i proveravanje ponašanja
digitalnih kola
“leksički analizator” tipičnog kompajlera, tj.
kompajlerska komponenta koja deli ulazni tekst u
logičke delove kao što su identifikatori, ključne reči i
punktuacija.
21
Software
za skeniranje velikih delova teksta, kao što
je kolekcija web stranica, kako bi se iznašlo
pojavljivanje reči, fraza ili drugih obrazaca.
Software za verifikaciju sistema svih tipova koje imaju
konačan broj različitih stanja, kao što su
komunikacioni protokoli za sigurnu rezmenu
informacija.
22
Pre davanja precizne definicije automata različitog tipa,
započnimo neformalan uvod, šta je to konačna
automatizacija i šta radi?
Ima mnogo sistema i komponenata, kao što su primeri
koje smo maločas izlistali, koji se mogu videti kao da su
sve vreme u jednom od konačnog broja stanja.
Svrha stanja je da zapamti odgovarajući deo istorije
sistema. Pošto postoji samo konačan broj stanja – cela
istorija se generalno ne može zapamtiti, tako da se
sistem mora pažljivo projektovati da bi zapamtio ono što
je važno i zaboravio ono šta nije.
23
Koja je prednost imanja konačnog broja stanja?
Možemo implementirati sistem sa konačnim
skupom resursa!
Primer: mogli bismo implementirati hardware
kao el. kolo, ili kao jednostavan oblik programa
koji može donositi odluke tražeći samo
ograničenu količinu podataka ili koristeći poziciju
u samom kodu da bi se donela odluka.
24
Primer 1
Najjednostavnija netrivijalna konačna automatizacija je on/off
prekidač. (uredjaj pamti da li je u on ili off stanju, i dozvoljava
korisniku da pritisne dugme čiji je efekat različit, u zavisnosti od
stanja prekidača – ako je prekidač u off stanju, tada se pritiskom na
dugme, menja u on stanje, i obrnuto)
Slika 1: Modeliranje konačnom automatizacijom on/off prekidača
25
Označavanje
Model konačne automatizacije dat je na Slici 1. Kao i za sve
konačne automate, stanja su predstavljena krugovima. U ovom
primeru stanja smo imenovali sa on i off. Lukovi izmedju stanja su
označeni sa ulazima, koji predstavljaju spoljašnje uticaje na sistem.
Ovde, oba luka su označena sa ulazom Push, koji predstavlja
korisnika koji pritiska dugme. Namera dva luka je da bez obzira u
kom stanju je sistem, kada je Push primljeno, odlazi u drugo stanje.
Jedno od stanja je označeno kao početno stanje, tj. stanje u koje se
sistem stavlja inicijalno. U našem primeru početno stanje je off, i po
konvenciji početno stanje se indicira sa rečju Start i strelicom koja
vodi u to stanje.
26
Često je potrebno naglasiti jedno ili više stanje kao
konačno ili prihvatno stanje. Ulaskom u jedno od ovih
stanja nakon sekvence ulaza pokazuje se da je ulazna
sekvenca dobra na neki način. Na primer, na Slici 1 smo
mogli smatrati stanje on kao stanje prihvatno, zato što će
u tom stanju, uredjaj koji je kontrolisan prekidečem,
raditi.
Po konvenciji prihvatno stanje se obeležava duplim
krugom, iako to nije naznačeno na Slici 1.
27
Primer 2
Ponekad, ono što se pamti stanjem može biti
složenije nego on/off izbor.
Slika 2 pokazuje drugu konačnu automatizaciju
koja može biti deo leksičkog analizatora.
Slika 2. Konačna automatizacija koje modeluje
prepoznavanje reči then
28
Zadatak ove automatizacije je da prepozna reč
then. Otuda, on zahteva pet stanja, svako od
kojih predstavlja različitu poziciju u reči then koja
je do tog trenutka dostignuta. Ove pozicije
odgovaraju prefiksima reči, od prazne reči do
kompletne.
29
Jednostavan kompjuter
ID A
K
E
PR
Č
BATERIJA
ulaz: prekidač
izlaz: sijalica
akcija: f za pritisni prekidač
stanja: on, off
30
Jednostavan “kompjuter”
ID
EK
R
P
AČ
f
BATERIJA
start
on
off
f
ulaz: prekidač
izlaz: sijalica
Sijalica je uključena ako i
samo ako je postojao
neparan broj pritiskanja
akcija: f za pritisni prekidač
stanja: on, off
31
Drugi “kompjuter”
1
1
start
2
BATERIJA
off
off
1
2
2
2
1
2
off
on
1
ulaz: prekidači 1 i 2
akcija:
1 za pritisni prekidač 1
2 za pritisni prekidač 2
Sijalica je uključena ako i
samo ako su oba
prekidača pritisnuta
neparan broj puta
stanja: on, off
32
Problem projektovanja
1
4
5
BATERIJA
2
3
=
Projektujmo kolo gde je svetlo upaljeno samo kada
su svi prekidači pritisnuti isti broj puta.
33
Problem za projektovanje
Ovakvi uredjaji su teški za rezonovanje, jer se
mogu projektovati na beskonačan broj načina
f
on
off
f
Njihovim predstavljanjem kao abstraktnog
računskog uredjaja, ili automata, naučićemo kako
da odgovorimo na ta pitanja
34
Ovi uredjaji mogu modelovati
mnogo problema
Oni mogu opisati operacije bilo kog malog
kompjutera, kao što je upravljačka komponenta
alarma ili mikrotalasne pećnice
Takodje se koriste u leksičkim analizatorima radi
prepoznavanja dobro definisanih izraza
programskih jezika:
ab1
5u=
je legalno ime za varijablu u C-u
nije
35
Različite vrste automata
Ovo je bio samo jedan primer računskog
uredjaja, a ima i drugih
Posmatraćemo različite uredjaje, i odgovarati na
sledeća pitanja:
Koje vrste problema može dati tip uredjaja
rešiti?
Koje stvari su nemoguće za ove vrste
uredjaja?
Da li je jedan tip uredjaja moćniji od drugog?
36
Neki uredjaji sa kojima ćemo se sresti
Konačni automati
Uredjaji sa konačnom količinom memorije.
Koriste se da modeliraju “male” kompjutere.
Pritisni automati
Uredjaji sa neograničenom memorijom kojima se može
prići na restriktovan način.
Koriste se za modelovanje parsera, itd.
Turing-ove mašine
Uredjaji sa neograničenom memorijom. Koriste se da
modeluju kompjuter.
Vremenski-ograničene
Turing-ove mašine
Neograničena memorija, ali ograničeno vreme
procesiranja.
Koriste se za modelovanje bilo kog kompjuterskog
programa koji se izvršava u razumnom vremenu.
37
Pregled kursa
Konačni automati
Razumećemo
koje vrste problema uredjaj sa
konačnom memorijom može uraditi, a koje ne može
Uvešćemo simulaciju: sposobnost jednog uredjaja da
imitira drugi uredjaj
Uvešćemo nedeterminizam: sposobnost uredjaja da
pravi proizvoljne izbore
38
Pregled kursa
Pritisni automati
Ovi
uredjaji su povezani sa gramatikama, koji
opisuju strukturu programiranja (i prirodne)
jezike
39
Pregled kursa
Turing-ove Mašine
Ovo
je generalni model kompjutera, obuhvatajući sve
što smo se ikad nadali da možemo izračunavati
Ali postoji i mnogo stvari koje kompjuteri ne mogu da
urade:
Za dati kod kompjuterskog programa, možete li reći
da li štampa reč “proba”?
#include <stdio.h>
main(t,_,a)char *a;{return!0<t?t<3?main(-79,-13,a+main(-87,1-_,
main(-86,0,a+1)+a)):1,t<_?main(t+1,_,a):3,main(-94,-27+t,a)&&t==2?_<13?
main(2,_+1,"%s %d %d\n"):9:16:t<0?t<-72?main(_,t,
"@n'+,#'/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l,+,/n{n+,/+#n+,/#\
;#q#n+,/+k#;*+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l \
q#'+d'K#!/+k#;q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;# \
){nl]!/n{n#'; r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#n'wk nw' \
iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c \
;;{nl'-{}rw]'/+,}##'*}#nc,',#nw]'/+kd'+e}+;#'rdq#w! nr'/ ') }+}{rl#'{n' ')# \
}'+}##(!!/")
:t<-50?_==*a?putchar(31[a]):main(-65,_,a+1):main((*a=='/')+t,_,a+1)
:0<t?main(2,2,"%s"):*a=='/'||main(0,main(-61,*a,
"!ek;dc [email protected]'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"),a+1);}
?
proba
40
Pregled kursa
Vremenski-ograničene Turing-ove Mašine
Mnoge probleme je moguće rešiti na kompjuteru u principu, ali
uzimaju mnogo vremena u praksi
Putujući prodavac: Za datu listu gradova, pronaći najkraći put da
se poseti i vratiti se kući
Grad E
Grad A
Grad F
Grad D
Grad B
Grad C
Lak u principu: Pokušajte proći gradove u svakom mogućem
redosledu
Težak u praksi: Za 100 gradova, trebalo bi 100+ godina čak i na
najbržem računaru!
41
Osnove teorije automata
Kako možemo formalizovati pitanje
Može li uredjaj A da reši problem B?
Najpre, potreban nam je način da opišemo
probleme koje smo zainteresovani da
rešimo
42
Problemi
Primeri problema koje ćemo razmotriti
Za datu reč s, da li sadrži podreč lepo?
Za dati broj n, da li je deljiv sa 7?
Za dati par reči s i t, da li su isti?
Za dati izraz sa zagradama, pr. (()()), da li se svaka
leva zagrada uklapa sa narednom desnom zagradom?
Svi ovi primeri imaju da/ne odgovor.
Postoje drugi tipovi problema, kao što su pronaći ovo ili
Koliko toga ali nećemo razmatrati te slučajeve.
43
Na Slici 2. pet stanja su označena sa
prefiksom od then koje su do tada vidjene.
Ulazi odgovaraju slovima.
44
Možemo zamisliti da leksički analizator ispituje jedan
karakter programa koji se kompajlira u tom trenutku, a
sledeći karakter koji treba da se ispita je ulaz u
automatizaciju.
Početno stanje odgovara praznom stringu, i svako stanje
ima prelaz na sledeće slovo od then u stanje koje
odgovara sledećem – većem prefiksu.
Stanje koje je označeno sa then je dostignuto kada je
ulaz spelovao reč then. Pošto je zadatak ove
automatizacije da prepozna kada je reč then vidjena,
možemo smatrati to stanje jedinim prihvatnim stanjem.
45
Strukturalne reprezentacije
Postoje još dva važna pojma koja igraju važnu ulogu u
proučavanju automatizacije i njihovih aplikacija:
1. Gramatike su korisni modeli pri projektovanju software-a
koje procesiraju podatke sa rekurzivnim strukturama.
Najpoznatiji primer je parser, komponenta kompajlera
koja radi sa rekurzivno ugnježdenim karakteristikama
tipičnih programskih jezika, kao što su izrazi –
aritmetički, kondicionalni, itd.
Na primer, gramatičko pravilo kao što je E⇒E+E kaže
da se izraz može formirati uzimanjem bilo koja dva
izraza i njihovim povezivanjem sa plus znakom;
46
ovo pravilo je tipično za način kako se izrazi u
realnom programiranju formiraju. Uvodimo
kontekstno-slobodne gramatike, kao što se
uobičajeno zovu, u Poglavlju 5.
2. Regularni izrazi takodje označavaju strukturu podataka,
pogotovu stringove teksta. Kao što ćemo videti u
Poglavlju 3, obrasci stringova koje opisuju su tačno
isti kao oni što se znaju opisati konačnim
automatima. Stil ovih izraza se razlikuje značajno od
gramatike, i sada ćemo izložiti jednostavan primer.
47
Regularni izraz u UNIX-u
`[A-Z][a-z]*[ ][A-Z][A-Z]`
predstavlja reč koja počinje velikim slovom praćena
prazninom i sa dva velika slova. Ovaj izraz predstavlja
obrazac u tekstu koji može biti grad ili država, npr. Ithaca
NY. On ne obuhvata imena gradova sa više reči, kao
što je Paolo Alto CA, koji se, pak, može obuhvatiti
složenijim izrazom
`[A-Z][a-z]*(`[A-Z][a-z] *) *[ ][A-Z][A-Z]`
48
Pri interpretaciji ovakvih izraza, treba samo da
znamo da [A-Z] predstavlja rang karaktera od
velikog slova A do velikog slova Z, tj. bilo koje
veliko slovo, i da se [ ] koristi da predstavlja
prazno mesto. Takodje, simbol * predstavlja bilo
koji broj ponavljanja prethodnog izraza. Zagrade
se koriste za grupisanje komponenti izraza, oni
ne predstavljaju karaktere koji su opisani.
49
Automati i složenost
Automati su esencijalni za proučavanja granica
izračunavanja. Kao što smo pomenuli u uvodu
ovog poglavlja, postoje dva važna pitanja:
1. Šta kompjuter može uraditi uopšte? Ova
studija se naziva odlučivost (eng. decidability) i
problemi koji se mogu rešiti pomoću kompjutera
se nazivaju odlučivi. Ova oblast će se proučavati
u Poglavlju 9.
50
2. Šta kompjuter može uraditi efikasno? Studija
se naziva netraktabilnost (eng. intractability) i
problemi koji se mogu rešiti pomoću kompjutera
koristeći ne više vremena od sporo rastuće
funkcije veličine ulaza se naziva traktabilnost.
Često uzimamo sve polinomijalne funkcije da su
sporo rastuće, dok funkcije koje rastu brže od
bilo koje polinomijalne se smatraju da rastu
previše brzo. Ova tema se proučava u Poglavlju
10.
51
Centralni koncepti teorije automata
Dalje, uvodimo najvažnije definicije izraza kojima
obiluje teorija automata.
Ovi koncepti uključuju:
Azbuku - skup simbola,
Stringove, tj. reči - lista simbola formirana od slova azbuke,
Jezik - skup reči iz istog alfabeta.
52
Azbuka (alfabet)
Def. Azbuka je konačan, neprazan skup simbola.
Konvencionalno, koristimo simbol Σ za azbuku.
Uobičajena azbuka uključuje
1.
Σ={0,1}, binarna azbuka
2.
Σ={a,b,...z}, skup svih malih slova
3.
skup svih ASCII karaktera, ili skup svih ASCII karaktera
koji se mogu štampati
53
Stringovi
Def. String (ili reč) je konačna sekvenca simbola
izabrana nad nekom azbukom.
Primer: 01101 je string od binarne azbuke Σ={0,1}.
String 111 je primer drugog stringa izabranog iz
iste azbuke.
Prazan string
Prazan string je string sa nula javljanja simbola. Ovaj
string, u oznaci ε je string koji se može izabrati iz bilo
koje azbuke.
54
Dužina stringa
Često je korisno klasifikovati stringove prema njihovoj
dužini, tj. prema broju pozicija za simbole u stringu. Na
primer, 01101 ima dužinu 5. Uobičajeno je reći da je
dužina stringa broj simbola u stringu; ova izjava se
prihvata ali nije najkorektnija. Reč ima samo dva simbola
0 i 1, u stringu 01101, ali ima 5 pozicija za simbole i
njihova dužina je 5. Medjutim, može se generalno
očekivati da se broj simbola može koristiti kada se broj
pozicija podrazumeva.
55
Standardna notacija za dužinu stringa ω je | ω |.
Na primer,
| 011 |=3
|ε |=0.
56
Stepen azbuke
Ako je Σ azbuka, možemo izraziti skup svih
stringova odredjene dužine iz te azbuke
korišćenjem eksponencijalne notacije.
Definišemo Σk kao skup stringova dužine k, čiji svaki simbol
je u Σ.
Primer: Zapazimo da je Σ0={ε}, bez obzira koja azbuka je u
pitanju.
To jest, ε je jedini string čija je dužina jednaka 0.
57
Primer: Ako je Σ={0,1},
onda Σ1={0,1}, Σ2={00,01,10,11},
Σ3={000,001,010,011, 100,101,110,111}, itd.
Zapazimo da eventualno postoji mala nejasnoća
oko Σ i Σ1.
Prvo je azbuka i njeni članovi su simboli 0 i 1.
Drugo je skup svih stringova dužine 1, i njegovi
članovi su 0 i 1.
58
Nećemo pokušavati da koristimo različitu notaciju
za ova dva skupa, oslanjajući se na kontekst koji
razjašnjava da li je {0,1} ili sličan skup azbuka ili
skup simbola.
Skup svih stringova nad azbukom Σ se konvencionalno označava sa Σ*.
Na primer {0,1}*={ε, 0, 1, 00, 01, 10, 11, 000,...},
tj. zapisano na drugi način
Σ*= Σ0U Σ1U Σ2U...
59
Ponekad, želimo da isključimo prazan
string iz skupa stringova.
Skup nepraznih stringova od azbuke Σ se
označava sa Σ+.
Stoga su dve odgovarajuće ekvivalencije
Σ+=Σ1UΣ2UΣ3 i Σ*=Σ+{0}.
60
Konkatenacija stringova
Neka su x i y stringovi. Onda xy označava konkatenaciju od
x i y, tj. string formiran od x praćen sa y.
Preciznije, ako je x string komponovan od i simbola
x=a1a2...ai i y je string komponovan od j simbola
y=b1b2...bj, onda xy predstavlja string dužine i+j:
xy=a1a2...aib1b2...bj.
Primer: Neka je x=01101 i y=110. onda xy=01101110 i
yx=11001101. Za bilo koji string ω, jednačina εω=ωε=ω
važe. To jest, ε je jedinica za konkatenaciju, jer kada se
konkatenira sa bilo kojim stringom kao rezultat daje taj
string. (analogno sabiranju sa 0, svaki broj x sabran sa
0, daje x)
61
Jezici
Def. Skup stringova od kojih su svi izabrani iz
neke Σ*, gde je Σ odredjena azbuka, naziva se
jezik.
Ako je Σ azbuka i L⊆Σ*, onda je L jezik nad Σ.
Zapazimo da jezik nad Σ ne treba da uključuje
stringove sa svim simbolima u Σ, tako da kada
jednom želimo da je L jezik nad Σ, takodje
znamo da je to jezik nad bilo kojom azbukom
koja je nadskup od Σ.
62
Izbor izraza za jezik može izgledati stran. Medjutim,
uobičajeni jezici se mogu videti kao skupovi stringova.
Jedan primer je Engleski jezik, gde je kolekcija legalnih
engleskih reči skup stringova nad azbukom koja se
sastoji od svih slova.
Drugi primer je C programski jezik, ili bilo koji drugi
programski jezik, gde je važeći program podskup
mogućih stringova koji se mogu formirati od azbuke
jezika. Ova azbuka je podskup ASCII karaktera, ali
generalno uključuje velika i mala slova, brojeve,
punktuaciju, i matematičke simbole.
63
Medjutim, postoji takodje i drugi jezici koji se
javljaju pri proučavanju teorije automata.
Neki su abstraktni primeri, kao što su:
1. Skup svih stringova koji se sastoje od n 0-la
praćenih sa n 1-ca, za neko n≥0:
{ε,01,0011,000111,...}
2. Skup stringova 0-la i 1-ca sa jednakim brojem
istih {ε,01,10, 0011,0101,1001,...}
3. Skup binarnih članova čija vrednost je prost broj
{10,11,101,111,1011...}
64
4. Σ* je jezik za bilo koju azbuku Σ.
5. ∅, prazan jezik, je jezik nad bilo kojom azbukom
6. {ε}, jezik koji se sastoji od samo prazne reči je
takodje jezik nad azbukom. Zapazimo da ∅≠ {ε},
∅ nema stringova, a slovo ε ima jedan string.
65
Problem
U teoriji automata, problem je pitanje da li je
dati string član nekog odredjenog jezika.
Sve što mi kolokvijalno nazivamo problemom se
može izraziti kao članstvo u jeziku.
Primer: Ako je Σ azbuka, i L jezik nad Σ, onda je
problem L:
Za dati string ω i Σ*, odlučiti da li je ili ne ω u L.
66
Primer
Problem testiranja da li je neki broj prost ili ne se može
izraziti preko jezika Lp koji se sastoji od svih binarnih
stringova čija vrednost kao binarnog člana je prost broj.
Tj. za dati string 0-la i 1-ca, odgovor je da ako je string
binarna reprezentacija prostog broja, i odgovor je ne ako
nije.
Za neke stringove, ova odluka je laka. Na primer, 0011101
se ne može predstaviti prostim brojem, iz prostog
razloga što svaki ceo broj osim 0 ima binarnu
reprezentaciju koja počinje sa 1. Medjutim, manje je
očigledno da li string 11101 pripada Lp-u, tako da će bilo
koje rešenje ovog problema trebati da koristi značajne
resurse neke vrste vreme i/ili prostor, na primer.
67
Jedan potencijalno nezadovoljavajući aspekt
odlučivanja (da ili ne) (da li je ili nije sledeće tačno?)
jeste zahtev da se izračuna ili transformiše neki ulaz
(pronaći najbolji način da se to uradi) u pitanje.
Na primer, zadatak parsera u C-kompajleru se može učiti
kao problem u formalnom smislu, gde je nekom dat
ASCII string i pita se da odluči da li je ili ne string član Lc,
skupa validnih C-programa.
68
Medjutim, parser radi više od odlučivanja. Ono proizvodi
drvo parsiranja, ulaze u tabele, simbole i možda i više.
Čak šta više, kompajler rešava problem prevodjenja Cprograma u kod objekta za neku mašinu, koji je daleko
od jednostavnog odgovora da ili ne o validnosti
programa.
Bez obzira na to, definicija problema kao jezika je izdržala
test vremena kao odgovarajući način da se izbori sa
pitanjima teorije složenosti.
69
U ovoj teoriji, mi smo zainteresivani za dokazivanje
da je granica složenosti odgovarajući problem.
Posebno važne su tehnike za dokazivanje da se
odredjeni problemi ne mogu rešiti u vremenima
koja su manja od eksponencijalnog preko
veličine ulaza. Ispostavlja se da su da/ne ili
jezička verzija poznatih problema teški u ovom
smislu, kao njihove rešiti ovo verzije.
70
Ukoliko možemo dokazati da je teško odlučiti da li je dati
string u jeziku Lx validnih stringova u programskom
jeziku X, onda je pristup (ali neće biti lakše) da se
translira program u jezik X (u objektni kod).
Ako se generiše kod, onda bi mogli pokrenuti translator, i
zaključiti da je ulaz validni član od Lx ukoliko je translator
uspeo da proizvede kod objekta.
Pošto konačni korak za odredjivanje da li je kod objekta
proizveden, nije težak, možemo koristiti brže algoritme
za generisanje koda objekta da bi odlučili članstvo u Lx
na efikasniji način.
71
Stoga, protivurečimo pretpostavku da je testiranje članstva
u Lx teško.
Imamo dokaz protivurečenjem izjave, ako je testiranje
članstva u Lx teško, onda je kompajliranje programa
jezika X teško.
Ova tehnika, koja pokazuje jedan problem teškim
korišćenjem njegovog pretpostavljenog efikasnog
algoritma da bi se efikasno rešio drugi problem koji je
već poznat da je težak, naziva se redukcijom drugog
problema u odnosu na prvi. To je važan alat u
proučavanju složenosti problema, i uveliko je olakšan
našom notacijom da je problem pitanje o članstvu u
jeziku, radije nego opšte vrste pitanja.
72
Konačni automati
73
Primer konačne automatizacije
f
on
off
f
Postoje stanja off i on, automatizacija započinje u
off i pokušava da dostigne prihvatno stanje on
Koje sekvence od f-ova vode ka prihvatnom
stanju?
Odgovor: {f, fff, fffff, Y} = {f n: n je neparan}
Ovo je konačna automatizacija nad alfabetom {f}
74
Deterministički konačni automati
Deterministička konačna automatizacija (DFA) je 5-očlani
skup (Q, Σ, δ, q0, F) gde
Q predstavlja konačni skup stanja
Σ je alfabet
δ: Q × Σ → Q je funkcija prelaza
q0 ∈ Q je početno stanje
F ⊆ Q je skup prihvatnih stanja (ili konačnih stanja).
Na dijagramima, prihvatna stanja se označavaju duplim
krugovima
75
Primer
q0
1
1
q1
azbuka Σ = {0, 1}
stanja Q = {q0, q1, q2}
početno stanje q0
Prihvatna stanja F = {q0, q1}
0,1
0
q2
Tabela funkcije prelaza δ:
ulazi
stanja
0
q0
q1
q2
0
q0
q2
q2
1
q1
q1
q2
76
Jezik DFA
Jezik DFA (Q, Σ, δ, q0, F) je skup svih stringova nad Σ
koji, počinjući u q0 i prateći prelaze kako se string čita
sa leva na desno, dostižu neko prihvatno stanje.
f
M:
on
off
f
Jezik od M je {f, fff, fffff, Y} = {f n: n je neparan}
77
Primeri
S = {0, 1}
b
a
0
q0
S = {a, b}
q0
1
q1
a
1
q1
b
0
b
0
q0
q3
a
q2
q1
b
q4
1
1
a
b
a
0, 1
0
q2
Koji su jezici ovih automata?
78
Primeri
Konstruisati DFA nad azbukom {0, 1} koja
prihvata sve stringove sa najviše tri 1-ce
79
Primeri
Konstruisati DFA nad azbukom {0, 1} koja
prihvata sve stringove sa najviše tri 1-ce
Odgovor
0
0
q0
1
q1
0
1
q2
0, 1
0
1
q3
1
q4+
80
Primeri
Konstruisati DFA koji prihvata jezik
L = {010, 1}
( S = {0, 1} )
81
Primeri
Konstruisati DFA koji prihvata jezik
L = {010, 1}
Odgovor
q0
1
( S = {0, 1} )
0
q01
q010
0
0
qε
1
0, 1
1
q1
0, 1
qdie
0, 1
82
Primeri
Konstruisati DFA nad azbukom {0, 1} koji
prihvata sve stringove koji završavaju na
101
83
Primeri
Konstruisati DFA nad azbukom {0, 1} koji
prihvata sve stringove koji završavaju na
101
Putokaz: DFA mora zapamtiti poslednja 3
bita stringa koja čita
84
Primeri
Konstruisati DFA nad azbukom {0, 1} koji
prihvata sve stringove koji završavaju sa
0
101
0
q
Skica odgovora:
1
0
q0
1
q00
1
q01
…
1
q101
qε
1
0
q1
1
q10
q11
…
1
q001
…
0
…
000
q111
1
85
Hvala na pažnji.
86
Download

Teorija algoritama, jezika i automata