Formálne jazyky^Automaty ^ ^ Formálne jazyky 11 Automaty G IB110 Podzim 2010 1 Formálne jazyky^Automaty ^ ^ Jednosmerné TS alebo konečné automaty i TS sú robustné voci modifikáciám ■ existuje modifikácia, ktorá zmení (zmenSí) výpoCtovU silu TS? ■ áno, modifikácia ale musí ohraniCit výpoCtový zdroj Turingovho stroja polýnomialný Cas trieda P polýnomialný priestor trieda PSPACE (triedý P a PSPACE su mensie neZ trieda rozhodnutelných problemov) jeden smer pohýbu na paske ohranicenie spoava v tom, ze TS nema moznost vratii; sa k informacii, ktoru uz raz precital a ani nema moznost si o preatanom useku uchovat; kompletnu informaciu (riadiaca jednotka ma len konečný pocet stavov) = konecne automatý IB110 Podzim 2010 2 Formálne jazyky^Automaty ^ ^ Konečné automaty ■ vstupný reťazec sa číta zl'ava doprava, symbol po symbole ■ prečítaný symbol sa neprepisuje ■ výpočet sa zastaví po prečítaní posledneho symbolu alebo v situácii, ked' prechodový diagram neumoZňuje Žiadny d'alsí krok ak sa vypočet zastaví po prečítaní celeho vstupu v stave YES, znamena to odpoved' „/Áno" (konečny automat akceptuje vstup); ak sa vípočet zastaví v inom stave alebo sa zastaví a nieje prečítany cely vstup, znamena to odpoved' „Nie" (automat zamieta vstup) IB110 Podzim 2010 3 Formálne jazyky^Automaty ^ ^ Konečné automaty - dolné odhady Problém rozhodnul!, ci daný reťazec obsahuje rovnaký pocet symbolov a, Tvrdenie Neexistuje koneCný automat, ktorý rieSi tento problem. Dôkaz Sporom. Predpokladajme, Ze existuje automat F, ktorý problem rieSi. OznaCme N poCet stavov automatu F. Uvazme vstupný retazec, ktorý obsahuje presne N + 1 sýmbolov a, za ktorými nasleduje presne N + 1 sýmbolov b. Pri cítaní úvodnej sekvencie a-cok musia být dve polícka, ktore automat cíta v tom istom stave (pocet políčok je N + 1, pocet stavov je N). Výtvorme nový vstupný retazec tak, ze odstranime vsetký sýmbolý medzi týmito dvoma a-ckami (viz obrazok). Vúpocet na novom vstupnom retazci skoncí v tom istom stave a v tej istej pozícii ako výpocet na pôvodnom vstupnom retazci. Ak automat akceptuje obidva retazce dostavame spor (modifikovaný retazec nemý požadovaní vlastnost). Naopak, ak automat obidva retazce zamieta - spor (pôvodný retazec mí požadovaný vlastnost). IB110 Podzim 2010 4 Formálne jazyky^Automaty ^ ^ slav s \a a a a a a i- fc b ŕ; "1 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 YES! (správne NO\) automat pocita presne ako na pôvodnej postupnosti IB110 Podzim 2010 5 Formálne jazyky^Automaty ^ ^ Konečné automaty ako model systému s udalosťami Formálne jazyky^Automaty ^ ^ Konečné automaty - terminológia pojem jazyka ako ekvivalentu pojmu rozhodovací problém regulárny jazyk regularne vyrazy IB110 Podzim 2010 7 Formálne jazyky^Generatľvne výpočtové modely ^ ^ Formálne jazyky Ai Generatívne výpočtové modely IB110 Podzim 2010 8 Formálne jazyky^Generatľvne výpočtové modely ^ ^ Generatívne výpočtové modely Fixujme rozhodovací problém P (resp. jazyk P/) e urCit, Ci pre daný vstup X je odpoved' „/Áno" alebo „Nie" (resp. urcit, ci X patrí do jazyka Lx) e vymenoval! vSetký vstupý, pre ktore je odpoved' „/Áno" (resp. vymenovat všetky slová jazyka P/) Motivacia navod, ako výtvorit „správný" ret!azec formaina gramatika IB110 Podzim 2010 9 Formálne jazyky;>Generativne výpočtove modely ^ ^ Formálne gramatiky príklad IB110 Podzim 2010 10 Formálne jazyky^Generatľvne výpočtové modely ^ ^ Formálne gramatiky - vlastnosti Fakt Trieda jazykov generovaných formálnymi gramatikami je prave trieda rozhodnutelných probiemov. Formalne gramatiky s obmedzeniami y retazec na l'avej strane pravidla je nieje dlhSí neZ retazec na pravej strane pravidla y na l'avej strane kazdeho pravidla je práve jeden neterminálny symbol reguláarne gramatiky IB110 Podzim 2010 11 Formálne jazyky^Generatľvne výpočtové modely ^ ^ Formálne gramatiky - problém syntaktickej analýzy Pre danú formálnu gramatiku a reťazec rozhodnul!, Ci je slovo sa gramatikou vygenerovat!. rozhodnul:, či program v programovacom jazyku (definovanom gramatikou) je syntakticky správny Probiem syntaktickej analýzy je CiastoCne rozhodnutelný pre formalne gramatiky rozhodnutelný pre kontextove gramatiky polynomialne riesitel'ny pre bezkontextove gramatiky je doleZitá, aby sme pre definíciu syntaxe programovacieho jazyka použili čo najjednoduchší typ gramatiky IB110 Podzim 2010 12