Meillä on työpaikalla erikseen basic research ja advanced research. Basic ei tarkoita alkeita vaan perustutkimusta.
Se joukkokunta, jossa liikun, on advanced. Tuon sanan käyttäminen viittaa usein siihen, että tutkinnot on suoritettu eli että useimmat ovat tohtoreita.
Melkein kaikki ne, jotka kirjoittavat korkeakouluista ja tohtoritulvasta ja työttömyyteen kouluttamisesta, ovat väärässä.
Tohtorin tutkinto oli joskus sellaista hienoa, ja turhamaisuustutkintoja tehdään edelleen, enimmäkseen kuitenkin Yliopistolla.
Tekniikan ja kaupan alalla teoreetikot ja käytännön ihmiset riitelivät noin sata vuotta, ja ”insinööritohtorin” tutkintoa pidettiin Suomessakin outona ja luultavasti tarpeettomana.
En puhu siitä nyt enempää. Sanon vain, että tutkimuksen eli ”teorian” ja käytännön välinen raja on lopullisesti samentunut. Olen siitä iloinen.
Ihannemaani Yhdysvaltojen patenttiasioiden muutoksenhakutuomiostuimessa (Court of Appeal for Federal Circuit) kaikki jäsenet ovat oikeudellisten tutkintojen lisäksi suorittaneet tohtorin tutkinnon luonnontieteissä, useat kemiassa, muutamat fysiikassa, monet tietotekniikassa.
Perustietämyksen tason on noussut noin korkealle. Tosin amerikkalainen Ph.D. ei ole yleensä yhtä vaativa kuin suomalainen FT.
Halusin sanoa vain muutaman sanan alkeista.
Heräte tuli sähköpostin kirjamainoksesta – Aarnion ja Kankaan Testamenttioikeudesta on tullut uusi laitos.
Erästä epämiellyttävää asiaa varten jouduin kertaamaan samojen tekijöiden Suomen Jäämistöoikeuden, joka siis käsittelee enimmäkseen perintöä.
Perintöasiat ovat hovioikeudessa suhteellisen harvinaisia. En toisin sanoen osaa niitä enkä ole juuri joutunut tekemisiin vuosikymmeniin. Ammattikunnan sisällä vallitsee luullakseni sellainen käsitys, että varsinkin vaikeat perintöasiat on syytä jättää eksperttien käsiin.
Kaipaisin oppilaitani varten kirjaa, jonka nimi olisi Siviilioikeuden yleiset opit. Myös Sopimusoikeuden perusteet kelpaisi. Mika Hemmon Sopimus ja delikti melkein on sellainen kirja.
Suurenmoisin kertauskirja ja johdatus vaikeisiin ja tärkeisiin peruskysymyksiin on ruotsinmaalainen Grönforsin oikeustoimilain kommentaari (Avtalslagen). Tavattoman hieno ja aivan välttämätön on saman tekijän Avtal och omförhandling – alle 100 sivua. Ja Avtalsgrundade rättsfakta.
Uskoisitte kerrankin, muidenkin, minkä tahansa alan ihmiset. Parhaat ammattilaiset ottavat kerran pari vuodessa lyijykynän ja viivoittimen ja kertaavat alkeita. Tai siis perusteita.
Niitä ei opi koskaan kunnolla. Sen takia vanhojen professorien on syytä luennoida johdantokursseja. Ne ovat niin vaikeita.
Panen kuvaksi lyijykynä- ja viivotinkirjan tietojenkäsittelystä. Se ei ole ohjelmistoista eikä ohjelmoinnista, vaan algoritmeista ja niiden todistamisesta. En ymmärrä siitä paljonkaan, mutta jotain, ainakin finiittisistä kielistä ja säännöllisistä ilmauksista (RegEx). Ja automaattien teoria viehättää.
Jos vankilaan saisi viedä mukaansa vain yhden kirjan, tämä olisi ehdolla.
Ei nyt ole kuitenkaan sellaista tilannetta näköpiirissä.
Eikö Hemmon ja Aurejärven "Velvoiteoikeuden oppikirja" (2007) kelpaa?
VastaaPoistaJuristeille sopisi myös mainiosti oheisopiskeltavaksi model theory , jonka Stanfordin Encyclopedia of Philosophy määrittelee seuraavasti: "Model theory began with the study of formal languages and their interpretations, and of the kinds of classification that a particular formal language can make. Mainstream model theory is now a sophisticated branch of mathematics (see the entry on first-order model theory). But in a broader sense, model theory is the study of the interpretation of any language, formal or natural, by means of set-theoretic structures, with Alfred Tarski's truth definition as a paradigm. In this broader sense, model theory meets philosophy at several points, for example in the theory of logical consequence and in the semantics of natural languages."
VastaaPoistaSillä olisi välitön vaikutus lainsäädännön ja laintulkinnan laatuun.
Taitaapa Wilfrid Hodgesin perusteos Model Theory löytyä ilmaiseksi googlen kirjastosta ja reilulla parillasadalla dollarilla paperille painettuna kirjakaupoista.
Hajamielinen professori(John Wawrzynek) löytyy täältä http://webcast.berkeley.edu/course_details.php?seriesid=1906978272
VastaaPoistamutta ei hän harhaan johda, suuret linjat ovat hallussa, hajamielisyys kohdistuu yksityiskohtiin. Miten opiskelija sen sitten voisi tietää?
Kiva että Iso K tuntuu olen samoilla linjoilla tästä ns. ylikoulutuksesta.
VastaaPoistaTunnen aina taantumuksen hyisen viiman sielussani, kun kuulen ihan fiksulta näyttävien korkeastikin koulutettujen ihmisten esittävän mielipiteitä, joiden sanoma on se, että "kuka sitten suoritusportaan työt tekee, jos koko ikäluokka koulutetaan ylioppilaiksi?"
Tällainen kysymys esitettiin viimekin vuonna. Usein väitettä vielä tehostetaan faktalla, ettei koko ikäluokalla kerta kaikkiaan ole älyllistä kapasiteettia korkeampaan oppiin.
Kauhistun, koska täysin samalla argumentaatiolla vastustettiin meilläkin aikanaan rahvaan koulutusta ja ennen kaikkea tyttöjen koulutusta - ja tätä viimeksi mainittua tehdään edelleenkin aika monessa maassa.
Eli täysin vastaava lause kuin kysyä "Mihin yhteiskunta muka tarvitsee tohtoreita?" on kysyä "Mitä perheenäiti muka tarvitsee lukutaitoa?".
Tapsa kirjoitti: "Usein väitettä vielä tehostetaan faktalla, ettei koko ikäluokalla kerta kaikkiaan ole älyllistä kapasiteettia korkeampaan oppiin."
VastaaPoistaNiinpä. Ongelma on ehkä siinä, että meillä kuitenkin vielä elää vanha maailma ("Tohtorin tutkinto oli joskus sellaista hienoa"), joka määrää, millainen osaaminen on arvostettavampaa ja korkeampaa kuin jokin toinen. Minusta se on outoa. En muista koskaan kadehtineeni yhtä ainutta tohtoria. Monia käsistään käteviä - oppiarvosta riippumatta - kadehdin jatkuvasti.
Se kuvitelma, että koko ikäluokalla ei riitä älyllistä kapasiteettia johonkin, johtunee osin siitä, että älyllinen kapasitetti määritellään ja mitataan niin kapeasti. Ei ole mikään salaisuus, että peruskoulussa menestyvät ne, jotka muistavat asioita lukemalla. Lukeminen on yksi tapa oppia. Jos lukeminen jollekulle ei ole omin tapa oppia, hänestä tulee helposti "erityisoppilas". Se on hyvä asia, jos koulussa sattuu olemaan erityisopettaja, joka ymmärtää, että oppimisessa kannattaa kokeilla muitakin tapoja. En ole vakuuttunut siitä, että joka koulussa on. Tiedän lahjakkaita lapsia, jotka säännöllisesti saavat kokeesta kiitettävän numeron, jos heille jaksaa tehdä ääninauhan koealueesta. Ellei jaksa, arvosana on luultavasti hylätty.
Minusta Sinun, Kemppinen, kannattaisi ottaa sinne vankilaan mieluummin virkkausvälineet. Vai kudotaanko niitä pannulappuja? Jatkaisit kuitenkin äitisi kunniakasta taitoa.
On mukava tehdä lomalla kaikenlaista pikku hommaa, rakennella puuhuussia omasta päästä jne. Kaikkea sitä touhua jota pojat puuhasivat jo pieninä. Majoja ei tehdä puuhun, mutta tehdään grillikatos, laituri ja muuta mukavaa. Lopputulos on tekijänsä näköinen, joka ollee ärhäkin kriitikko.
VastaaPoistaVuosikymmenet korvienvälissä työtä tehneenä kiehtoo ajatus tehdä oikeita töitä vaikkapa rakennuksella. Ensin verollisessa palkkatyössä valoisan aikaan, sitten pimeissä hommissa hämärän aikaan ja talven pimeydessä kortistossa ja etelän lämmössä.
Off topic:
VastaaPoistaItaliassa asian perillemenoon vaaditaan korkeimman oikeuden päätös: Juttu
Kun olen ollut esimiehenä parille tohtorille, olen huomannut, että koulutus ei välttämättä häiritse kovin paljoa työntekoa.
VastaaPoistaAntti, Antti - älä ihannoi "oikeita" töitä.
VastaaPoistaAikoinani Kainuun korvessa rakennustyömaalla 20 asteen pakkasessa lapio kädessä routaista maata kuopiessani päätin pyhästi, että sisätöihin on päästävä, maksoi mitä maksoi,
Vähästäpä sitä ihminen sielunsa myy.
Oppiminen on helppoa. Sen sijaan opitusta pois pääseminen ei ole niinkään yksinkertaista. Ihmisen tulisikin suojella itseään ulkoaopitulta tiedolta, sellainen tieto nimittäin toimii estona omien aivojen elämässä.
VastaaPoistaAd JarmoM
VastaaPoistaKeneltä Pratosta?
Prato on kehno paikka ostaa puuvillaa, mutta villakankaitten tuottajia siellä on aika hyviä.
Lanificio Alman kokoelma on minusta... naisellinen on väärä sana, ämmämäinen sopii paremmin.
Riccerin kokoelma on hyvä ja kallis. Alle 50€ metrihinnan heiltä ei saa edes kylmää katsetta.
Marcello Cortesta en sano mitään.
Gardena on edullinen, mutta se näkyy laadussa, jos kohta on heillä ollut tähtihetkensä. Kutomo on sen verran nuori, etteivät he vielä ole ehtineet vakiinnuttaa asemaansa.
Pantexin Kappa herringbone ja Bristol ovat erittäin hyviä kankaita, mutta Pantex ei tee puuvillasta mitään.
Figli Di Michelangelon koko kokoelmassa ei ole kuin yksi kangas, johon koskisin.
Zanieri olisi alueen paras paitakangasvalmistaja, mielestäni, mutta heidänkään kokoelmassa ei ole aluspaitakankaita. Minulta saa heidän valkoista paitapellavaansa hintaan 76€ metri.
Bonacchin puuvillakankaat ovat erittäin hyviä, kokoelma on laaja ja monipuolinen, mutta hintava, eikä siinä ole alusvaatetrikoota.
Tele di Camars tekee kyllä puuvillasta, mutta ei alusvaatekankaita.
Cecchillä saattaisi olla alusvaatekankaitakin, mutta epäilen.
Praton alueella on paljon hyviä kutomoja, mutta näin muistin varaisesti ei kyllä tule mieleeni yhtään neuleita valmistavaa laitosta alueella. Toki sitten Gruppa Romalla on puuvillajerseytä tekevä laitos, mutta se on muistaakseni Bulgariassa. Minimierä taitaa olla 600 metriä per väri.
Kannattavan tuotannon logistiikka on sitten asia sinänsä. Valkovenäjällä ja Ukrainassa kannattaa tuottaa jos sarjat ovat suuria, mutta pienempiin sarjoihin kannattaa sitten kääntyä Aasian. Nepal ja Sri Lanka ovat suhteellisen kilpailukykyisiä hinta-, tulli- ja kuljetusehtojen puolesta. Kiina on hieman arvaamaton byrokratian puolesta, samoin pitää olla suhteet mutta sieltäkin löytyy valmistajia jotka nöyrtyvät muutaman tuhannen kappaleen pieneriin jos he odottavat saavansa pitkäaikaisen asiakasuhteen.
Shanghain messuilta kannattaa kysellä lisää Kiinasta, sitten minulla olisi yksi paikka Beijingissä, mutta osaan sinne kävellen Wangfungilta, mutta en muista firman nimeä, joka voisi myös tulla kysymykseen. Ulospäin talo näyttää asuintalolta.
Singapore ja Thaimaa ovat hieman hintapaineessa, mutta eivät vielä ulkona kokonaan.
Intiasta en osaa sanoa kovin paljoa, mutta paljonhan sieltä tulee tavaraa.
Ei se tuo bloggarinkaan homma järin palkitsevaa ole. Ensin yrittää kirjoittaa viisaita ja filosohvisia juttuja, mutta kansa onkin kiinnostuneempi puuhuussin tekemisestä päästä ja vankilaan viemisistä.
VastaaPoistaHyviä ja tarpeellisia tietoja ovat nekin. Ehkä tärkeämpiäkin kuin jotkin korkeasti oppineiden tuomaristohtoreiden jutut.
Luin hiljan vanhan pohjanmaalaisen timpurin puuhuussin valmistusohjeet. Painotti, että on tärkeää juntata ainakin yksi nurkka syvälle maahan, etteivät naapurin kollit pysty kaatamaan laitosta kesken suorituksen.
Ihannemaa Amerikassa tavallisilla lääkelääkäreillä on tapana mainostaa itseään lisäämällä nimensä perään M.D. eli medical doctor painottamaan homman erityistä ylevyyttä samaan tapaan kuin Ph.D.
Hyvähän se toki on, jos osaa hommansa ja tietää mitä lääkettä kellekin syöttää ja neuloo joutessaan irronneen sormen tai sellaisen takaisin paikoilleen.
Tunsin kerran kaverin, joka lääkäreiden esimerkin rohkaisemana painatti käyntikortin nimensä perään P.W. Oli lyhenne sanoista "published writer" ja halusi vetää eroa pelkkiin pöytälaatikkokirjailijoihin. Oli nimittäin saanut yhden runon julkaistuksi paikallislehdessä.
Ajatus on mielestäni hyvä, jos tekijä tuntee alemmuutta kylillä. Esimerkkejä hyvistä olisi pilvin pimein.
Mitä vankilaan tulee, niin mukaan ottaisin korvatulpat.
Petjalle:
VastaaPoistaJa se on JarMom, eikä JarmoM, stana.
Sama pratolainen perheyritys, joka tuottaa kankaita mm. Marimekolle, aikoinaan Kuopioon ja mitä näitä nyt onkaan. Perheyrityksen nuorempi poika F.
Jonain salaisuutena muistelisin, että kiinalaiset, joita Praton tehtailla paljon työskentelee, olisi jollain tavalla näppinsä mukana "kankaiden salakuljetuksessa". Iso rulla "t-paitaa" mulle kerran annettiin...made in Italy, mutta valmistettu Kiinassa :):)
Hys, hys, ei saa muille kertoa.
Olihan listassasi tuttuja nimiäkin.
Hmmmmmm...
Kemppinen kirjoitti: "Tohtorin tutkinto oli joskus sellaista hienoa, ja turhamaisuustutkintoja tehdään edelleen, enimmäkseen kuitenkin Yliopistolla."
VastaaPoistaKäsittelemättä asiaa laajemmin ja ilman sivuajatuksia (pun intended) todettakoon, että Kemppisen oma tohtorintie näyttää ainakin meistä entisistä luento-oppilaista peräti poikkeavalta: varsin kunniallista urakehitystä edennyt käytännön tuomari, joskin kirjailijana ja kulttuuri-ilmiönä laajalti tunnettu, teki työn kautta hyvin tuntemastaan aihepiiristä väitöskirjan nykyisiin keskiarvoihin verrattuna jo varttuneena. Saimme hänestä mainion dosentin, mutta tohtorius oli kuitenkin monien silmissä vain pikantti lisämauste tavalla, joka ei olisi vailla vertailukohtia. Mutta sitten, suomalaisittain hyvin poikkeuksellisesti, hän vaihtoi kokonaan uraa ja hänestä sukeutui todellinen ammattitiedemies ja aivan raakaa opetus- ja ohjaustyötäkin tekevä professori.
PS Kemppinen käytti ("yhden miehen juhlakulkueenkin" puheenparteen sopivasti) termiä "Yliopisto". Pöytäkirjaa varten totean, että turhamaisuutta esiintyy myös maakuntayliopistoissa.
Kemppinen kirjoitti: "Parhaat ammattilaiset ottavat kerran pari vuodessa lyijykynän ja viivoittimen ja kertaavat alkeita. Tai siis perusteita. "
VastaaPoistaHear, hear!
Jo lukion laajan matematiikan tunneilla taottiin jatkuvan kertaamisen tärkeys, ja peruskaavat olenkin sitten vuosittain kerrannut, vaikka pallon tilavuudella tai derivoinnilla ei nyt niin ratkaisevaa merkitystä työssäni olekaan. Kummallista, miten kaavoista kumminkin aina jotain uuttakin huomaa. Samoin on välttämätöntä vähintään selata toistakymmentä toimintapiirinsä tärkeintä lakia ja muuta säädöstä vuosittain ajantasaisena läpi, se käy mukavasti esimerkiksi lomalla laiturilla; pienellä vaivalla saa ison hyödyn.
Kemppinen kirjoitti: "Kaipaisin oppilaitani varten kirjaa, jonka nimi olisi Siviilioikeuden yleiset opit. Myös Sopimusoikeuden perusteet kelpaisi."
TH vastasi: "Eikö Hemmon ja Aurejärven "Velvoiteoikeuden oppikirja" (2007) kelpaa?"
Hemmon Sopimusoikeus on mainio käsikirjan ja monografian väli-ilmiö, nyt jo III-osaiseksi paisuneena tosin jo Kemppisen mainitsemaan tarpeeseen liian laaja. Mutta WSLT, Talentum, Tietosanoma & co ovat kyllä kiitettävästi lisänneet peruskatsaustenkin määrää.
Mutta persoonallista, tiivistä timanttia ei ole aikoihin tainnut näkyä.
Tämä on se taustalla oleva matematiikka ilmeisesti, jonka takia me emme enää näe yli tietyn hierarkian (ja näin ajateltuna Gödelin teoreema rupeaa saamaan merkityksiä, joilla on merkitys myös tieteelle: annapa joku matemaattikko katsoo ja kirjoittaa yhteiskunta/ihmistieteilijän kanssa kunnon analyysi tai järkeen käyvä vertaus (ei liian monimutkainen vaan ihan metafoorallinen, poliittinen) sillä minä uskon, että dataa seurataan erilailla eri hierarkioista mm Aasiassa missä merkkiteoriat ovat 2000 edellä ja kaikenlaisten kvasi-jumalien teot on takanapäin kuten alkemistin jne (älä julkaise tätä):
VastaaPoistaAutomata theory
From Wikipedia, the free encyclopedia
• Learn more about citing Wikipedia •
Jump to: navigation, search
"Automata" redirects here. For a self-operating machine, see Automaton.
In theoretical computer science, automata theory is the study of abstract machines and problems they are able to solve. Automata theory is closely related to formal language theory as the automata are often classified by the class of formal languages they are able to recognize.
An automaton is a mathematical model for a finite state machine (FSM). A FSM is a machine that, given an input of symbols, "jumps" through a series of states according to a transition function (which can be expressed as a table). In the common "Mealy" variety of FSMs, this transition function tells the automaton which state to go to next given a current state and a current symbol.
The input is read symbol by symbol, until it is consumed completely (think of it as a tape with a word written on it, that is read by a reading head of the automaton; the head moves forward over the tape, reading one symbol at a time). Once the input is depleted, the automaton is said to have stopped.
Depending on the state in which the automaton stops, it's said that the automaton either accepts or rejects the input. If it landed in an accept state, then the automaton accepts the word. If, on the other hand, it lands on a reject state, the word is rejected. The set of all the words accepted by an automaton is called the language accepted by the automaton.
Note, however, that, in general, an automaton need not have a finite number of states, or even a countable number of states. Thus, for example, the quantum finite automaton has an uncountable infinity of states, as the set of all possible states is the set of all points in complex projective space. Thus, quantum finite automata, as well as finite state machines, are special cases of a more general idea, that of a topological automaton, where the set of states is a topological space, and the state transition functions are taken from the set of all possible functions on the space. Topological automata are often called M-automata, and are simply the augmentation of a semiautomaton with a set of accept states, where set intersection determines whether the initial state is accepted or rejected.
In general, an automaton need not strictly accept or reject an input; it may accept it with some probability between zero and one. Again this is illustrated by the quantum finite automaton, which only accepts input with some probability. This idea is again a special case of a more general notion, the geometric automaton or metric automaton, where the set of states is a metric space, and a language is accepted by the automaton if the distance between the initial point, and the set of accept states is sufficiently small with respect to the metric.
Automata play a major role in compiler design and parsing.
Contents
[hide]
* 1 Vocabulary
* 2 Formal description
* 3 Classes of finite automata
o 3.1 Extensions of finite automata
* 4 External links
* 5 References
[edit] Vocabulary
The basic concepts of symbols, words, alphabets and strings are common to most descriptions of automata. These are:
Symbol
An arbitrary datum which has some meaning to or effect on the machine. Symbols are sometimes just called "letters".
Word
A finite string formed by the concatenation of a number of symbols.
Alphabet
A finite set of symbols. An alphabet is frequently denoted by Σ, which is the set of letters in an alphabet.
Language
A set of words, formed by symbols in a given alphabet. May or may not be infinite.
Kleene closure
A language may be thought of as a subset of all possible words. The set of all possible words may, in turn, be thought of as the set of all possible concatenations of strings. Formally, this set of all possible strings is called a free monoid. It is denoted as Σ * , and the superscript * is called the Kleene star.
[edit] Formal description
An automaton is represented by the 5-tuple \langle Q, \Sigma, \delta, q_0, F\rangle, where:
* Q is a set of states.
* ∑ is a finite set of symbols, that we will call the alphabet of the language the automaton accepts.
* δ is the transition function, that is
\delta:Q \times \Sigma \rightarrow Q.
(For non-deterministic automata, the empty string is an allowed input).
* q0 is the start state, that is, the state in which the automaton is when no input has been processed yet (Obviously, q0∈ Q).
* F is a set of states of Q (i.e. F⊆Q), called accept states.
Given an input letter a\in\Sigma, one may write the transition function as \delta_a:Q\rightarrow Q, using the simple trick of currying, that is, writing δ(q,a) = δa(q) for all q\in Q. This way, the transition function can be seen in simpler terms: its just something that "acts" on a state in Q, yielding another state. One may then consider the result of function composition repeatedly applied to the various functions δa, δb, and so on. Repeated function composition forms a monoid. For the transition functions, this monoid is known as the transition monoid, or sometimes the transformation semigroup.
Given a pair of letters a,b\in \Sigma, one may define a new function \widehat\delta, by insisting that \widehat\delta_{ab}=\delta_a \circ \delta_b, where \circ denotes function composition. Clearly, this process can be recursively continued, and so one has a recursive definition of a function \widehat\delta_w that is defined for all words w\in\Sigma^*, so that one has a map
\widehat\delta:Q \times \Sigma^{\star} \rightarrow Q.
The construction can also be reversed: given a \widehat\delta, one can reconstruct a δ, and so the two descriptions are equivalent.
The triple \langle Q, \Sigma, \delta \rangle is known as a semiautomaton. Semiautomata underlay automata, in that they are just automata, where one has ignored the starting state and the set of accept states. The additional notions of a start state and an accept state allow automata to do something the semiautomata cannot: they can recognize a formal language. The language L accepted by a deterministic finite automaton \langle Q, \Sigma, \delta, q_0, F\rangle is:
L= \{ w \in \Sigma^{\star}\,|\;\widehat\delta(q_0,w)\in F\}
That is, the language accepted by an automaton is the set of all words w, over the alphabet Σ, that, when given as input to the automaton, will result in its ending in some state from F. Languages that are accepted by automata are called recognizable languages.
When the set of states Q is finite, then the automaton is known as a finite state automaton, and the set of all recognizable languages are the regular languages. In fact, there is a strong equivalence: for every regular language, there is a finite state automaton, and vice versa.
As noted above, the set Q need not be finite or countable; it may be taken to be a general topological space, in which case one obtains topological automata. Another possible generalization is the metric automata or geometric automata. In this case, the acceptance of a language is altered: instead of a set inclusion of the final state in \widehat\delta(q_0,w)\in F, the acceptance criteria are replaced by a probability, given in terms of the metric distance between the final state \widehat\delta(q_0,w) and the set F. Certain types of probabilistic automata are metric automata, with the metric being a measure on a probability space.
[edit] Classes of finite automata
The following are three kinds of finite automata
Deterministic finite automata (DFA)
Each state of an automaton of this kind has a transition for every symbol in the alphabet.
DFA
DFA
Nondeterministic finite automata (NFA)
States of an automaton of this kind may or may not have a transition for each symbol in the alphabet, or can even have multiple transitions for a symbol. The automaton accepts a word if there exists at least one path from q0 to a state in F labeled with the input word. If a transition is undefined, so that the automaton does not know how to keep on reading the input, the word is rejected.
NFA, equivalent to the DFA from the previous example
NFA, equivalent to the DFA from the previous example
Nondeterministic finite automata, with ε transitions (FND-ε or ε-NFA)
Besides of being able to jump to more (or none) states with any symbol, these can jump on no symbol at all. That is, if a state has transitions labeled with ε, then the NFA can be in any of the states reached by the ε-transitions, directly or through other states with ε-transitions. The set of states that can be reached by this method from a state q, is called the ε-closure of q.
It can be shown, though, that all these automata can accept the same languages. You can always construct some DFA M' that accepts the same language as a given NFA M.
[edit] Extensions of finite automata
The family of languages accepted by the above-described automata is called the family of regular languages. More powerful automata can accept more complicated languages. Such automata include:
Pushdown automata (PDA)
Such machines are identical to DFAs (or NFAs), except that they additionally carry memory in the form of a stack. The transition function δ will now also depend on the symbol(s) on top of the stack, and will specify how the stack is to be changed at each transition. Non-determinstic PDAs accept the context-free languages.
Linear Bounded Automata (LBA)
An LBA is a limited Turing machine; instead of an infinite tape, the tape has an amount of space proportional to the size of the input string. LBAs accept the context-sensitive languages.
Turing machines
These are the most powerful computational machines. They possess an infinite memory in the form of a tape, and a head which can read and change the tape, and move in either direction along the tape. Turing machines are equivalent to algorithms, and are the theoretical basis for modern computers. Turing machines decide/accepts recursive languages and recognize the recursively enumerable languages.
[edit] External links
* Visual Automata Simulator
* JFLAP
* dk.brics.automaton
* libfa
* Proyecto SEPa (in Spanish)
* Exorciser (in German)
[edit] References
* John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman - Introduction to Automata Theory, Languages, and Computation (2nd Edition)
* Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Part One: Automata and Languages, chapters 1–2, pp.29–122. Section 4.1: Decidable Languages, pp.152–159. Section 5.1: Undecidable Problems from Language Theory, pp.172–183.
* James P. Schmeiser, David T. Barnard (1995). Producing a top-down parse order with bottom-up parsing. Elsevier North-Holland.
Automata theory: formal languages and formal grammars Chomsky
hierarchy Grammars Languages Minimal
automaton
Type-0 Unrestricted Recursively enumerable Turing machine
n/a (no common name) Recursive Decider
Type-1 Context-sensitive Context-sensitive Linear-bounded
n/a Indexed Indexed Nested stack
n/a Tree-adjoining etc. (Mildly context-sensitive) Embedded pushdown
Type-2 Context-free Context-free Nondeterministic pushdown
n/a Deterministic context-free Deterministic context-free Deterministic pushdown
Type-3 Regular Regular Finite
Each category of languages or grammars is a proper subset of the category directly above it,
and any automaton in each category has an equivalent automaton in the category directly above it.