Preview only show first 10 pages with watermark. For full document please download

T /2 Tietojenkäsittelyteorian Perusteet T/y

T /2 Tietojenkäsittelyteorian perusteet T/Y Tietojenkäsittelytieteen laitos, Aalto-yliopisto Aalto-yliopisto Perustieteiden korkeakoulu Tietojenkäsittelytieteen laitos Syksy 2013 T /1002

   EMBED


Share

Transcript

T /2 Tietojenkäsittelyteorian perusteet T/Y Tietojenkäsittelytieteen laitos, Aalto-yliopisto Aalto-yliopisto Perustieteiden korkeakoulu Tietojenkäsittelytieteen laitos Syksy 2013 T /1002 Tietojenkäsittelyteorian perusteet T/Y Introduction to Theoretical Computer Science T/Y What can one do with a computer? This course divides roughly into three parts. We examine three models of a computer, their power and limitations, i.e., the classes of languages that they can decide. It turns out that each class of automata corresponds to a class of grammars. The classes of automata and grammars are: 1. Finite state automata & regular expressions 2. Pushdown automata & context-free grammars 3. Turing machines & unrestricted grammars The first teaching period of the course (=Y version) covers finite state automata, regular expressions and context-free grammars. The second period covers the rest. 2/295 Course versions There are two versions of the course for different kinds of students. If you are unsure which to take, check your study guide or ask your study advisor. T Introduction to TCS T, periods I-II, 4 cr compulsory in the computer science bachelor s program; in the Discrete Mathematics B1 module... T Introduction to TCS Y, period I, 2 cr compulsory in the communications engineering bachelor s program in ; part of supplementary studies for polytechnic graduates to enter computer science program part of supplementary studies for some Master s Programme students... 3/295 Practical arrangements Registration: obligatory, by OODI, deadline Sep 23, 2013 Lectures: Tue T1, in Finnish by Doc., D.Sc. Tommi Junttila Tutorials: once a week, register by OODI with course code T ; not obligatory but highly recommended! Fri Fri in English Mon Tue Wed See Noppa for class rooms etc. Computerized home assignments: obligatory and personalized. Distributed by after Sep 23th to those who registered to the course. Course Noppa pages: https://noppa.aalto.fi/noppa/kurssi/t / https://noppa.aalto.fi/noppa/kurssi/t / 4/295 To pass the course 1. Pass the computerized assignments before taking the exam. 2. After passing the computer exercises, take an exam (next exams in Oct 2013, Dec 2013, Feb 2014, May 2014). 3. There are 3 homework problems a week; you gain bonus points for exam according to table: # solved: T T N/A These bonus points are valid until December By completing the computer assignments by 09:00 on 24 Oct 2013, one can earn a bonus of 2 points for the exams. These do not help in making a failed exam passed. 5/295 PLEASE NOTICE: due to Bachelor s program renewal, In the future, this is the last time these two courses are organized. T will be terminated T will be replaced by the 5 credits course ICS-C2000 Theoretical Computer Science organized first time in Spring 2015 The last exams of T and T will be organized in December 2014 There will be no teaching (lectures, tutorials,...) during Autumn /295 Material Lecture notes aka Orposen pruju (in Finnish) is distributed through NOPPA Lecture slides (in Finnish) also on NOPPA Demonstration exercises and their solutions (both in Finnish and in English) are distributed through NOPPA Recommended textbook Michael Sipser, Introduction to the Theory of Computation (2nd Edition), (Supplementary for Finnish-speaking students; likely necessary for non-finnish-speaking students.) Some additional material on NOPPA. 7/295 TIETOJENKÄSITTELYTEORIA Matemaattinen oppi siitä, mitä tietokoneella on mahdollista tehdä ja kuinka tehokkaasti. Tarjoaa matemaattisia käsitteitä ja menetelmiä tietojenkäsittelyjärjestelmien mallintamiseen ja analysointiin sekä selkeiden ja tehokkaiden ratkaisujen laatimiseen. 8/295 Tietojenkäsittelyteorian osa-aloja Laskettavuusteoria Mitä tietokoneella voi tehdä periaatteessa? Turing, Gödel, Church, Post (1930-luku); Kleene, Markov (1950-luku). Laskennan vaativuusteoria Mitä tietokoneella voi tehdä käytännössä? Hartmanis, Stearns (1960-luku); Cook, Levin, Karp (1970-luku); Papadimitriou, Sipser, Håstad, Razborov ym. (1980-). Automaatti- ja kielioppiteoria Tietojenkäsittelyjärjestelmien perustyyppien ominaisuudet ja kuvausformalismit. Chomsky (1950-luku); Ginsburg, Greibach, Rabin, Salomaa, Schützenberger ym. (1960-luku) 9/295 Tietojenkäsittelyteorian osa-aloja Ohjelmien oikeellisuus Tietojenkäsittelyjärjestelmien matemaattisesti eksakti määrittely ja oikean toiminnan verifiointi. Dijkstra, Hoare (1960-luku); Manna, Pnueli, Scott ym. (1970-). Muuta algoritmien suunnittelu ja analyysi (Knuth, Hopcroft, Tarjan ym.) kryptologia (Rivest, Shamir, Adleman ym.) rinnakkaisten ja hajautettujen järjestelmien teoria (Lamport, Lynch, Milner, Valiant ym.) koneoppimisteoria (Valiant ym.) jne. Tällä kurssilla käsitellään lähinnä automaatteja ja kielioppeja sekä hieman laskettavuusteorian alkeita. Muita aiheita käsitellään muilla tietojenkäsittelyteorian (T 79) kursseilla. 10/295 1.1 Joukot Joukko (engl. set) on kokoelma alkioita. Alkiot voidaan ilmoittaa joko luettelemalla, esim. tai jonkin säännön avulla, esim. S = {2,3,5,7,11,13,17,19} S = {p p on alkuluku, 2 p 20}. Jos alkio a kuuluu joukkoon A, merkitään a A, päinvastaisessa tapauksessa a / A. (Esim. 3 S, 8 / S.) Tärkeä erikoistapaus on tyhjä joukko (engl. empty set) /0, johon ei kuulu yhtään alkiota. 11/295 Jos joukon A kaikki alkiot kuuluvat myös joukkoon B, sanotaan että A on B:n osajoukko (engl. subset) ja merkitään A B. [Kirjallisuudessa esiintyy myös merkintä A B.] Jos A ei ole B:n osajoukko merkitään A B. Siis esim. {2,3} S, {1,2,3} S. Triviaalisti on voimassa /0 A kaikilla A. Joukot A ja B ovat samat, jos niissä on samat alkiot, so. jos on A B ja B A. Jos on A B, mutta A B, sanotaan että A on B:n aito osajoukko (engl. proper subset) ja merkitään A B. Edellä olisi siis voitu myös kirjoittaa {2,3} S ja /0 A jos A /0. 12/295 Joukon alkioina voi olla myös toisia joukkoja (tällöin puhutaan usein joukkoperheestä ), esim. X = {/0,{1},{2},{1,2}}. Jonkin perusjoukon A kaikkien osajoukkojen muodostamaa joukkoperhettä sanotaan A:n potenssijoukoksi (engl. powerset) ja merkitään P (A):lla; esim. edellä on X = P ({1,2}). [Koska n-alkioisen perusjoukon A potenssijoukossa on 2 n alkiota (HT), käytetään kirjallisuudessa potenssijoukolle myös merkintää 2 A.] Huomaa, että A B jos ja vain jos A P (B). Tyhjän joukon käsittelyssä pitää olla huolellinen: /0 {/0}, P (/0) = {/0}, P ({/0}) = {/0,{/0}}. 13/295 Joukkoja voidaan kombinoida joukko-operaatioilla, joista tärkeimmät ovat: yhdiste (engl. union) A B = {x x A tai x B}, esim. {1,2,3} {1,4} = {1,2,3,4}. leikkaus (engl. intersection) A B = {x x A ja x B}, esim. {1,2,3} {1,4} = {1}. erotus (engl. difference) A B = {x x A ja x / B}, esim. {1,2,3} {1,4} = {2,3}. [Erotukselle käytetään myös merkintää A \ B.] 14/295 Joukko-operaatioita koskevat tietyt laskulait, joista tärkeimmät ovat yhdisteen ja leikkauksen liitännäisyys: ja vaihdannaisuus: sekä näiden osittelulait: A (B C) = (A B) C A (B C) = (A B) C A B = B A A B = B A A (B C) = (A B) (A C) A (B C) = (A B) (A C) 15/295 Jos kaikki tarkasteltavat joukot ovat jonkin yhteisen universaalijoukon U osajoukkoja, sanotaan erotusta U A joukon A komplementiksi (U:n suhteen) ja merkitään Ā:lla. Yhdiste-, leikkaus- ja komplementointioperaatioita yhdistävät tärkeät ns. de Morganin kaavat: A B = Ā B, A B = Ā B. Lisäksi joukkojen erotus voidaan esittää leikkauksen ja komplementoinnin avulla seuraavasti: A B = A B. 16/295 Jos joukkoperheen A jäsenet on indeksoitu, esim. A = {A 1,A 2,A 3,...}, niin yhdisteelle ja leikkaukselle voidaan käyttää lyhennemerkintöjä A i = A 1 A 2 A 3 i 1 ja A i = A 1 A 2 A 3 Indeksien ei tarvitse olla edes luonnollisia lukuja, vaan indeksijoukkona voi olla mikä tahansa joukko I. Tällöin käytetään merkintöjä i 1 A = {A i i I} ja A i, i I A i. i I 17/295 1.2 Relaatiot ja funktiot Olkoot A ja B joukkoja. Alkioiden a A ja b B järjestettyä paria (engl. ordered pair) merkitään (a, b). Huomaa, että joukkoina on aina {a,b} = {b,a}, mutta jos a b, niin järjestettyinä pareina on (a,b) (b,a). Joukkojen A ja B karteesinen tulo (engl. Cartesian product) määritellään A B = {(a,b) a A ja b B}, Esimerkki {1,2,3} {1,4} = {(1,1),(1,4),(2,1),(2,4),(3,1),(3,4)} {a,b} N = {(a,0),(b,0),(a,1),(b,1),(a,2),(b,2),...} {a,b} /0 = /0 18/295 Relaatio R joukolta A joukolle B on karteesisen tulon A B osajoukko: R A B. Jos (a,b) R, niin merkitään myös arb ja sanotaan että alkio a on relaatiossa (suhteessa) R alkioon b. Tätä infix-merkintää käytetään varsinkin silloin, kun relaation nimenä on jokin erikoismerkki, esim.,,,. Jos relaation R lähtöjoukko (engl. domain) A ja maalijoukko (engl. range) B ovat samat, so. R A A, sanotaan että R on relaatio joukossa A. 19/295 Relaation R A B käänteisrelaatio (engl. inverse relation) on relaatio R 1 B A, R 1 = {(b,a) (a,b) R}. Jos R A B ja S B C ovat relaatioita, niin niiden yhdistetty relaatio (engl. composite relation) R S A C määritellään: R S = {(a,c) b B s.e. (a,b) R,(b,c) S}. 20/295 Varsinkin jos joukot A ja B ovat äärellisiä, relaatiota R A B voi olla havainnollista tarkastella suunnattuna verkkona t. graafina, jonka solmuina ovat joukkojen A ja B alkiot ja solmusta a A on kaari ( nuoli ) solmuun b B, jos ja vain jos (a,b) R. Esimerkki Olkoon joukossa A = {a, b, c, d} määritelty relaatio R = {(a,b),(a,c),(b,d),(c,d),(d,d)}. Relaation R graafiesitys: Relaation R R graafiesitys: a b a b c d c d 21/295 Relaatio f A B on funktio, jos kukin a A on relaatiossa f täsmälleen yhden b B kanssa. Tällöin käytetään yleisten relaatiomerkintöjen sijaan tavallisesti merkintöjä f : A B ja f (a) = b. Funktioita koskee kaikki mitä edellä yleisesti on todettu relaatioista, mutta historiallisista syistä funktioiden yhdistäminen merkitään toisin päin kuin yleisten relaatioiden: jos f : A B ja g : B C ovat funktioita, niin niiden yhdistetty funktio määritellään kaavalla (g f )(a) = g(f (a)), so. relaatioina g f = {(a,c) b B s.e. f (a) = b,g(b) = c}. 22/295 Olkoon f : A B funktio. f on surjektio (engl. onto map), jos jokainen b B on jonkin a A kuva, so. jos f (A) = B. f on injektio (engl. one-to-one map), jos kaikki a A kuvautuvat eri alkioille, so. jos a a f (a) f (a ). f on bijektio, jos se on sekä injektio että surjektio, so. jos jokainen b B on yhden ja vain yhden a A kuva. 23/295 1.3 Ekvivalenssirelaatiot Ekvivalenssirelaatiot ovat matemaattisesti täsmällinen muotoilu sille yleiselle idealle, että oliot ovat keskenään samankaltaisia jonkin kiinnostavan ominaisuuden X suhteen. Ominaisuuteen X perustuva ekvivalenssirelaatio osittaa tarkasteltavien olioiden joukon ekvivalenssiluokkiin, jotka vastaavat ominaisuuden X eri arvoja. (Kääntäen mielivaltainen olioiden joukon ositus Π määrää tietyn abstraktin samankaltaisuusominaisuuden, nim. sen että oliot ovat samankaltaisia jos ne sijoittuvat samaan osituksen Π luokkaan.) 24/295 Osoittautuu, että yleinen samankaltaisuusrelaation idea voidaan kiteyttää seuraaviin kolmeen ominaisuuteen. Määritelmä 1.1 Relaatio R A A on 1. refleksiivinen, jos ara a A; 2. symmetrinen, jos arb bra a,b A; 3. transitiivinen, jos arb,brc arc a,b,c A. Määritelmä 1.2 Relaatio R A A, joka toteuttaa edelliset ehdot 1 3 on ekvivalenssirelaatio. Alkion a A ekvivalenssiluokka (relaation R suhteen) on R[a] = {x A arx}. Ekvivalenssirelaatioita merkitään usein R:n sijaan alkioiden samankaltaisuutta korostavilla symboleilla,, tms. 25/295 Esimerkki Olkoon A = {kaikki 1900-luvulla syntyneet ihmiset} ja arb voimassa, jos henkilöillä a ja b on sama syntymävuosi. Tällöin R on selvästi ekvivalenssi, jonka ekvivalenssiluokat koostuvat keskenään samana vuonna syntyneistä henkilöistä. Luokkia on 100 kappaletta, ja abstraktisti ne vastaavat 1900-luvun vuosia 1900,..., /295 Lemma 1.3 Olkoon R A A ekvivalenssi. Tällöin on kaikilla a,b A voimassa: Lemma 1.4 R[a] = R[b] joss arb. Olkoon R A A ekvivalenssi. Tällöin R:n ekvivalenssiluokat muodostavat A:n osituksen erillisiin epätyhjiin osajoukkoihin, so.: R[a] /0 kaikilla a A; A = a A R[a]; jos R[a] R[b], niin R[a] R[b] = /0, kaikilla a,b A. Kääntäen jokainen perusjoukon A ositus erillisiin epätyhjiin luokkiin A i, i I, määrää vastaavan ekvivalenssirelaation: a b a ja b kuuluvat samaan luokkaan A i. 27/295 1.5 Induktiopäättely Olkoon P(k) jokin luonnollisten lukujen ominaisuus. Jos on voimassa: 1. P(0) ja 2. kaikilla k 0: P(k) P(k + 1), niin P(n) on tosi kaikilla n N. 28/295 Esimerkki Väite. Kaikilla n N on voimassa kaava P(n) : ( n) 2 = n 3. Todistus. 1. Perustapaus: P(0) : 0 2 = 0. (jatkuu) 29/295 2. Induktioaskel: Oletetaan, että annetulla k 0 kaava P(k) : ( k) 2 = k 3 on voimassa. Tällöin on myös: ( k + (k + 1)) 2 = (1 + + k) 2 + 2(1 + k)(k + 1) + (k + 1) 2 = k 3 k(k + 1) + 2 (k + 1) + (k + 1) 2 2 = k 3 + k(k + 1) 2 + (k + 1) 2 = k 3 + (k + 1) 3. On siis todettu, että kaavan P(k) totuudesta seuraa kaavan P(k + 1) totuus, so. että P(k) P(k + 1), kaikilla k 0. Luonnollisten lukujen induktioperiaatteen 1.9 nojalla voidaan nyt päätellä, että kaava P(n) on voimassa kaikilla n N. 30/295 1.6 Aakkostot, merkkijonot ja kielet Automaattiteoria diskreetin signaalinkäsittelyn perusmallit ja -menetelmät ( diskreettien I/O-kuvausten yleinen teoria) 1011 Syöte Automaatti Tulos B Automaatin käsite on matemaattinen abstraktio. Yleisellä tasolla suunniteltu automaatti voidaan toteuttaa eri tavoin: esim. sähköpiirinä, mekaanisena laitteena tai (tavallisimmin) tietokoneohjelmana. 31/295 Tällä kurssilla keskitytään pääosin automaatteihin, joiden: 1. syötteet ovat äärellisiä, diskreettejä merkkijonoja 2. tulokset ovat muotoa hyväksy / hylkää ( syöte OK / syöte ei kelpaa ) Yleistyksiä: äärettömät syötejonot ( reaktiiviset järjestelmät, Büchi-automaatit) funktioautomaatit ( Moore- ja Mealy-tilakoneet, Turingin funktiokoneet) 32/295 Peruskäsitteitä ja merkintöjä Aakkosto (engl. alphabet, vocabulary): äärellinen, epätyhjä joukko alkeismerkkejä t. symboleita. Esim.: binääriaakkosto {0, 1}; latinalainen aakkosto {A,B,...,Z}. Merkkijono (engl. string): äärellinen järjestetty jono jonkin aakkoston merkkejä. Esim.: 01001, 0000 : binääriaakkoston merkkijonoja; TKTP, XYZZY : latinalaisen aakkoston merkkijonoja. tyhjä merkkijono (engl. empty string). Tyhjässä merkkijonossa ei ole yhtään merkkiä; sitä voidaan merkitä ε:llä. Merkkijonon x pituus x on sen merkkien määrä. Esim.: = 5, TKTP = 4, ε = 0. 33/295 Merkkijonojen välinen perusoperaatio on katenaatio eli jonojen peräkkäin kirjoittaminen. Katenaation operaatiomerkkinä käytetään joskus selkeyden lisäämiseksi symbolia. Esim. KALA KUKKO = KALAKUKKO; jos x = 00 ja y = 11, niin xy = 0011 ja yx = 1100; kaikilla x on xε = εx = x; kaikilla x, y, z on (xy)z = x(yz); kaikilla x, y on xy = x + y. 34/295 Aakkoston Σ kaikkien merkkijonojen joukkoa merkitään Σ :lla. Mielivaltaista merkkijonojoukkoa A Σ sanotaan aakkoston Σ (formaaliksi) kieleksi (engl. formal language). Esimerkki Jos Σ = {0,1}, niin Σ = {ε,0,1,00,01,10,11,000,...}. Esimerkki Jos Σ = {0, 1}, niin esimerkiksi seuraavat ovat aakkoston Σ kieliä: /0 {ε, 0, } {0,1,11,111,1111,...} Σ = {ε,0,1,00,01,10,11,000...} 35/295 Automaatit ja formaalit kielet Olkoon M automaatti, jonka syötteet ovat jonkin aakkoston Σ merkkijonoja, ja tulos on yksinkertaisesti muotoa syöte hyväksytään / syöte hylätään. (Merk. lyhyesti 1/0.) Merkitään M:n syötteellä x antamaa tulosta M(x):llä ja M:n hyväksymien syötteiden joukkoa A M :llä, so. A M = {x Σ M(x) = 1}. Sanotaan, että automaatti M tunnistaa (engl. recognises) kielen A M Σ. Automaattiteorian (yksi) idea: automaatin M rakenne heijastuu kielen A M ominaisuuksissa. Kääntäen: olkoon annettuna jokin toivottu I/O-kuvaus f : Σ {0,1}. Tarkastelemalla kieltä A f = {x Σ f (x) = 1} saadaan vihjeitä siitä, millainen automaatti tarvitaan kuvauksen f toteuttamiseen. 36/295 Vakiintuneita merkintöjä Em. matemaattisille käsitteille käytetyt merkinnät ovat periaatteessa vapaasti valittavissa, mutta esityksen ymmärrettävyyden parantamiseksi on tapana pitäytyä tietyissä käytännöissä. Seuraavat merkintätavat ovat vakiintuneet: Aakkostot: Σ, Γ,... (isoja kreikkalaisia kirjaimia). Esim. binääriaakkosto Σ = {0, 1}. Aakkoston koko (tai yleisemmin joukon mahtavuus): Σ. Alkeismerkit: a, b, c,... (pieniä alkupään latinalaisia kirjaimia). Esim.: Olkoon Σ = {a 1,...,a n } aakkosto; tällöin Σ = n. Merkkijonot: u, v, w, x, y,... (pieniä loppupään latinalaisia kirjaimia). 37/295 Merkkijonojen katenaatio: x y tai vain xy. Merkkijonon pituus: x. Esimerkkejä: Tyhjä merkkijono: ε. abc = 3; olkoon x = a 1...a m, y = b 1...b n ; tällöin xy = m + n. Merkkijono, jossa on n kappaletta merkkiä a: a n. Esimerkkejä: a n = } aa...a {{} ; n kpl a i b j c k = i + j + k. Merkkijonon x toisto k kertaa: x k. Esimerkkejä: (ab) 2 = abab; x k = k x. Aakkoston Σ kaikkien merkkijonojen joukko: Σ. Esim.: {a,b} = {ε,a,b,aa,ab,ba,bb,aaa,aab,...}. 38/295 Merkkijonoinduktio Automaattiteoriassa tehdään usein konstruktioita induktiolla merkkijonon pituuden suhteen. Tämä tarkoittaa, että määritellään ensin toiminto tyhjän merkkijonon ε (tai joskus yksittäisen aakkosmerkin) tapauksessa. Sitten oletetaan, että toiminto on määritelty kaikilla annetun pituisilla merkkijonoilla u ja esitetään, miten se tällöin määritellään yhtä merkkiä pitemmillä merkkijonoilla w = ua. Esimerkki. Olkoon Σ mielivaltainen aakkosto. Merkkijonon w Σ käänteisjono (engl. reversal) w R määritellään induktiivisesti säännöillä: 1. ε R = ε; 2. jos w = ua, u Σ, a Σ, niin w R = a u R. 39/295 Induktiivista ( rekursiivista ) määritelmää voidaan tietenkin käyttää laskujen perustana; esim.: (011) R = 1 (01) R = 1 (1 0 R ) = 11 (0 ε R ) = 110 ε R = 110 ε = 110. Tärkeämpää on kuitenkin konstruktioiden ominaisuuksien todistaminen määritelmää noudattelevalla induktiolla. Esimerkki: 40/295 Väite. Olkoon Σ aakkosto. Kaikilla x,y Σ on voimassa (xy) R = y R x R. Todistus. Induktio merkkijonon y pituuden suhteen. 1. Perustapaus y = ε: (xε) R = x R = ε R x R. 2. Induktioaskel: Olkoon y muotoa y = ua, u Σ, a Σ. Oletetaan, että väite on voimassa merkkijonoilla x, u. Tällöin on: (xy) R = (xua) R = a (xu) R [R:n määritelmä] = a (u R x R ) [induktio-oletus] = (a u R )x R [ :n liitännäisyys] = (ua) R x R [R:n määritelmä] = y R x R. 41/295 2.1 Tilakaaviot ja tilataulut Tarkastellaan aluksi tietojenkäsittelyjärjestelmiä, joilla on vain äärellisen monta mahdollista tilaa. Tällaisen järjestelmän toiminta voidaan kuvata äärellisenä automaattina t. äärellisenä tilakoneena (engl. finite automaton, finite state machine). Äärellisillä automaateilla on useita vaihtoehtoisia esitystapoja: tilakaaviot, tilataulut,... 42/295 Esimerkki: Kahviautomaatti 20 c 20 c 10 c 10 c 10 c 0,00 0,10 0,20 0,30 10 c enough 20 c 20 c 10 c 20 c more than enough! 10 c 20 c Em. tilakaavion esittämä automaatti ratkaisee päätösongelman riittävätkö annetut rahat kahvin ostamiseen? Äärellisiä automaatteja voidaan yleensäkin käyttää yksinkertaisten päätösongelmien ratkaisujen mallintamiseen. Automaattimallista on muitakin kuin binäärivasteisten järjestelmien kuvaamiseen tarkoitettuja versioita (ns. Moore- ja Mealy-automaatit), mutta niitä ei käsitellä tällä kurssilla. 43/295 Tilakaavioiden merkinnät: q Automaatin tila nimeltä q q 0 Alkutila q f Lopputila: automaatti hyväksyy syötejonon, joss se jonon loppuessa on tällaisessa tilassa q 1 a q 2 Syötemerkin a aikaansaama siirtymä tilasta q 1 tilaan q 2 44/295 Esimerkki C-kielen etumerkittömät reaaliluvut. q 7 digit. digit digit digit. digit q 0 q 1 q 2 q 3 exp exp exp digit q 4 digit q 6 +,- digit q 5 Käytetyt lyhenteet: digit = {0,1,...,9}, exp = {E,e}. 45/295 Äärellisen automaatin esitys tilatauluna: automaatin uusi tila vanhan tilan ja syötemerkin funktiona. Esimerkki Reaalilukuautomaatin tilataulu: digit. exp + q 0 q 1 q 7 q 1 q 1 q 2 q 4 q 2 q 3 q 4 q 3 q 3 q 4 q 4 q 6 q 5 q 5 q 5 q 6 q 6 q 6 q 7 q 3 missä ilmaisee alkutilaa ja lopputilaa. 46/295 K: Mitä tilataulun tyhjät paikat tarkoittavat? V: Tilataulun tyhjät paikat, tai vastaavasti tilakaavion puuttuvat kaaret, kuvaavat automaatin virhetilanteita. Jos automaatti ohjautuu tällaiseen paikkaan, syötejono ei kuulu automaatin hyväksymään joukkoon. Muodollisesti auto