TALEN EN AUTOMATEN 2002/03

dr. Peter van Emde Boas

tijden:
College   Maandag 11.15 -- 13.--   Zaal P 227    

Werkgroep AI  Dinsdag 11.15 -- 13.--   Zaal P018  ;   Practicumdocent Merlijn Sevenster  (email sevenstr@science.uva.nl)

Werkgroep INFO  Donderdag 11.15 -- 13.--   Zaal P019  ;   Practicumdocent Thijs van Remmen  (email tvremmen@science.uva.nl)
 

Agenda

Week   Maandag: college                                     Dinsdag werkgroep AI                                                             Donderdag  werkgroep INFO

 15        Apr 07   talen formeel en natuurlijk       Apr 08                                                                                       Apr 10
 16        Apr 14   Grammaticas                            Apr 15                                                                                       Apr 17
 17        Apr 21    valt uit: Pasen                          Apr 22   valt uit: Pasen                                                            Apr 24
 18        Apr 28    grammatica's cont.                  Apr 29                                                                                       Mei 01     valt uit:  dag van de Arbeid
  19        Mei 05    valt uit:  Nationalefeestdag     Mei 06                                                                                        Mei 08
  20        Mei 12    Turing machinemodel              Mei 13      valt uit:  zie studiegids                                              Mei 15     valt uit:  zie studiegids
  21        Mei 19    Varianten Turingmachine        Mei 20                                                                                        Mei 22
  22        Mei 26    Onbeslisbaarheid                      Mei 27                                                                                        Mei 29      valt uit:  Hemelsvaartdag
  23        Jun 02    Eindige Automaten                  Jun 03                                                                                        Jun 05
  24        Jun 09    valt uit:  Pinksteren                 Jun 10                                                                                        Jun 12
  25        Jun 16    Reguliere expressies                 Jun 17                                                                                        Jun 19
  26        Jun 23    Context Vrije grammaticas     Jun 24      tentamenperiode                                                       Jun 26     Vragenuur / proeftentamen
  27        Jun 30    tentamenperiode                      Jul 01       tentamenperiode                                                       Jul 03      tentamenperiode  
 28        Jul 07     tentamenperiode                      Jul 08       tentamenperiode                                                       Jul 10      tentamenperiode  
 
De eerste tentamengelegenheid zal zijn:  dinsdag 8 juli, 13.30 - 16.30, zaal  A.B

Het tentamen is een open boek tentamen: gebruik van syllabus en/of andere literatuur is toegestaan.
Geen laptops, palmtops of mobieltjes ed.

Een proeftentamen is beschikbaar in ps formaat en in pdf formaat.

Opgaven van het tentamen van 8 Juli jl. zijn te vinden op het web in  ps  formaat en pdf formaat.

Verwerking van de tentamenresultaten is vertraagd door het vacantieseizoen. De voorlopige lijst met
uitslagen (onder voorbehoud) is te vinden op het web in xls formaat.

De eerstvolgende herkansingsgelegenheid is woensdag 20 Augustus as  13.30 - 16.30  in zaal P - 227.

Opgaven van het tentamen van 20 Augustus zijn te vinden op het web in  ps  formaat en pdf formaat.

De lijst met uitslagen is hier aangegeven in xsl formaat.

De tweede en laatste herkansing is maandag 20 October 13.30 - 16.30  in zaal  A.D

Opgaven van het tentamen van 20 October zijn te vinden op het web in  ps  formaat en pdf formaat.

De lijst met uitslagen is hier aangegeven in xsl formaat.


Link naar de opgaven  
 

Inhoud van de Cursus:

Sommige problemen zijn simpel; ander juist zeer moeilijk. Door problemem te coderen als 'formele talen'  wordt hun moeilijkheidsgraad
beter vergelijkbaar.

Eenvoudige problemen, zoals patroonherkenning in eenntrekstverwerker, blijken dan oplosbaar op simpele machines die aan een eindig geheugen
genoeg hebben: 'eindige automaten' . Het herkennen van welgevormde uitdrukkingen in een computertaal vereist een complexere machine die
bekend staat onder de naam 'stapelautomaat' . Nog complexere probleme vragen om een onbegrensd herschrijfbaar geheugen zoals beschikbaar in het
model van de Turingmachine. Probleme zoals het vaststellen van de consistentie van Logische theorieen zijn zelfs voor deze machines te lastig: de probleme zijn onoplosbaar.

Formele talen laten zich ook classificeren door gebruik te maken van Grammatica's; dit staat bekend als de 'Chomsky Hierarchie'.  Doel van de cursus is te laten zien
hoe de verschillende formalismen van grammaticas en automaten met elkaar samenhangen en uiteindelijk dezelfde klassen van formele talen beschrijven.

Het vak Automatentheorie vervult in de Informatica een rol vergelijkbaar met die van de elementaire analyse en lineaire algebra in de Wiskunde en de Natuurkunde;
alle meer theoretisch gerichte informaticavakken maken gebruik van het begrippenapparaat van de Autmatentheorie.


 

Literatuur:

De cursus wordt verzorgd aan de hand van de syllabus: Autmatenetheorie van dr. P. van Emde Boas. Dit is een ongewijzigde herdruk van de syllabus die 
voor dit vak werd gebruikt in de periode 1982 - 1986. Hoewel aan de inhoud van het vak in de afgelopen twintig jaren weinig is veranderd geldt die niet voor
de wereld eromheen, en daardoor zijn details van de syllabus 'gedateerd'.  Opgaven zijn in deze syllabus slechts in geringe mate aanwezig, en voorzover aanwezig
vaak gericht op wiskunde studenten zoals die 20 jaar geleden aan deze instelling rondliepen. Daarom worden opgaven apart aangeboden, onder andere via het Web.

Bij het produceren van de syllabus blijkt in hoofdstuk 10 pagina 158 te zijn verdwenen. Dit is mij pas opgevallen tegen het einde van het college.
U kunt een scan  van de originele pagina ophalen in powerpoint formaat en in pdf.



Literatuur gebruikt bij eerdere jaargangen van deze cursus:

John E. Hopcroft & Jeffrey D. Ullman:  Formal Languages and their Relation to Automata, Addison Wesley, 1969

John E. Hopcroft & Jeffrey D. Ullman:  Introduction to Automata Theory, Languages and Computation, Addison Wesley, 1979

Harry R. Lewis & Christos H. Papadimitriou, Elements of the Theory of Computation, Prentice Hall, 1981

Thomas A. Sudkamp, Languages and Machines; an Introduction to the Theory of Computer Science, Addison Wesley, 1988

Thomas A. Sudkamp, Languages and Machines; an Introduction to the Theory of Computer Science, 2nd edition, Addison Wesley, 1997

Peter Linz, An Introduction to Formal Languages and Automata, D.C. Heath, 1990


Commentaar achteraf  (juni 2003)

Het gebruik van de syllabus levert de ervaring op dat de afgelopen twintig jaar toch het een en ander gebeurd is dat de syllabus gedateerd maakt. Ik doel daarbij niet op verwijzingen
naar de politieke toestanden in het Koninkrijk der Nederlanden die, zij het met andere poppetjes, twintig jaar geleden even bedroevend waren als heden.

Allereerst: Waar niemand rond 1984 rekening mee hield is gebeurd: het Fermat vermoeden is bewezen door Andrew Wiles rond 1995. Ieder gebruik van dit probleem
als prototype van een onopgelost probleem in de getaltheorie is daarmee achterhaald.

De aan het einde van ch. 2 besproken Lindemayer systemen zijn tegenwoordig vrijwel vergeten. Op deze plaats zou ht. een bespreking van Cellulaire Automaten meer op zijn plaats
zijn geweest.

In hoofdstuk  6  komt het probleem aan de orde of  deterministische LBA's en nondeterministische LBA's dezelfde klasse van talen herkennen. Dit probleem staat nog steeds open.
Het mogelijke gevolg van gelijkheid, inhoudende dat de klasse van nondeterministische LBA talen gesloten is onder complementatie is echter wel opgelost en wel in bevestigende zijn.
Deze stelling van Immerman en Szelepcsenyi is het voornaamste resultaat dat in deze syllabus had thuisgehoord, gesteld dat ik deze nu zou hebben geschreven. Gelukkig bestaate er een
artikel uit 1987 verschenen in een toenmalig studentenblad (de Wilde Tilde)  waarin het bewijs  wordt uitgelegd op een wijze passend bij de stijl van de syllabus. Dat document is nog
electronisch toegankelijk gebleken en kan dus thans op het web worden geplaatst.  (in ps  en in pdf formaat).  Het bewijs is overigens ook te vinden in het boek van Papadimitriou
dat hieronbder wordt vermeld. Szelepcsenyi's versie van het bewijs is verschenen als:  R. Szelepcsenyi, the method of forcing for nondeterministic automata, Bull EATCS 33 (1987) 96--100.

Onderzoek naar Algebraisch axiomatische theorieen voor de reguliere algebra is ook de afgelopen twintig jaren doorgegaan.  Een belangwekkend resultaat op dit gebied is de
volledige axiomatisering via conditionele vergelijkingen van Dexter Kozen uit 1994:  Dexter Kozen, A completeness Theorem for Kleene Algebras and the Algebra of Regular
Events, Inf. and Comput. 110 (1994) 366-390.  Het onderzoeksgebied Procesalgebra dat een ruime mate van overlap met deze algebraische theorie heeft moest 20 jaar geleden nog
worden ontwikkeld.

Tot nog toe heb ik mijzelve slechts op een enkele echte fout kunnen betrappen. Bij de behandeling van de gelijkwaardig CSL = NLBA als modificatie van de gelijkwaardigheid  RE = TM
is er bij de laatste gelijkheid sprake van talen geaccepteerd door Turingmachines terwijl er bij de eerste gelijkheid sprake is van talen herkend door NLBA's. Consequentie van deze
vervanging van accepteren door herkenning is dat wij ervoor moeten zorgen dat de berekeningen van de simulerende NLBA altijd termineren. Dit kan door naast de berekening een klok
mee te simuleren die een simulatie afsluit als deze zolang duurt dta wel herhaling van zetten moet zijn opgetreden. Deze esssentiele stap in de redenering ontbreekt in de syllabus maar staat
wel correct vermeld in het bovengenoemde verhaal over de Immerman-Szepelcsenyi stelling.




Beschikbare collecties transparanten in Powerpoint:

De hier vermeldde collecties transparanten zijn gebruikt bij andere colleges en worden hier slechts vermeld als extra informatie.
De voertaal van deze transparanten is Engels.

Onderwerp:  Know thy  Numbers:
                Beschikbaar in  Powerpoint98 format  and  pdf format
 

Verwante iteratuur: 
 

Berekenbaarheidstheorie

David Harel, Algorithmics; the Spirit of Computing, (second Edition),
Addison Wesley 1992.

A miniature version of this material appears in:
David Harel, Computers Ltd. ; what they really can't do,
Oxford Univ. Press, 2000

Christos H. Papadimitriou, Computational Complexity,
Addison Wesley 1995.
 
 

Overige colleges van deze docent:

dr. Peter van Emde Boas:  Theoretical Models (1st trimester): Games and Computer Science

dr. Peter van Emde Boas:  Berekenbaarheids en complexiteitstheorie (2nd trimester): Complexity and Computation Theory

dr. Peter van Emde Boas:  Intelligent Databases / Game Theory (3rd trimester): Intelligent Databases