Talen kunnen natuurlijke talen zijn (Nederlands, Engels), maar evengoed programmeertalen zoals de taal Java. Wie een zin uit bijvoorbeeld het Nederlands wil vertalen in een andere taal, zoals het Engels, heeft een grondige kennis nodig van zowel de structuur (syntaxis) als de betekenis (semantiek) van de twee talen. Als een vertaling door een computer moet worden uitgevoerd, dan moeten de syntaxis en semantiek op de een of andere manier formeel worden vastgelegd. Dat is voor natuurlijke talen een zeer lastige zaak. Formele talen, zoals programmeertalen, hebben een veel eenvoudigere structuur, die geautomatiseerd kan worden gecontroleerd. Die structuur wordt vastgelegd in een grammatica of in een automaat.

In deze cursus komen verschillende soorten formele talen met de bijbehorende grammatica's en automaten aan de orde. Ook wordt aandacht besteed aan het zelf ontwerpen van deze grammatica's en automaten.
Het eerste blok vormt een algemene inleiding op formele talen.
In het tweede blok worden de eigenschappen van reguliere talen en van eindige automaten behandeld. Context-vrije talen en stapelautomaten zijn het onderwerp van blok drie. In het laatste blok komen Turingmachines, de Chomsky-hiërarchie en de begrippen beslisbaarheid en complexiteit van problemen aan de orde.

Na het volgen van deze cursus kun je:

• aangeven wat een formele taal is en het verband uit te leggen tussen automaten, talen en grammatica's
• een globale indeling van formele talen op eigenschappen maken
• de belangrijkste eigenschappen van reguliere en context-vrije talen benoemen en gebruiken
• concrete voorbeelden van de volgende manieren om talen te beschrijven interpreteren, construeren en transformeren: reguliere expressies, eindige automaten, reguliere grammatica’s, context-vrije grammatica’s, stapelautomaten en turingmachines
• de begrippen berekenbaarheid, beslisbaarheid, complexiteit, P, NP en NP-compleet omschrijven
• reducties en eenvoudige transformaties gebruiken
• praktische toepassingen van de theorie noemen.

Je staat een 7 gemiddeld voor de vakken in jouw opleiding en je hebt 60 of meer studiepunten gehaald op het moment van het inleveren van de leerovereenkomst. Een cijferlijst moet bij de leerovereenkomst toegevoegd worden.

De leerovereenkomst wordt op de ingangseisen gecontroleerd. Daarna krijg je bericht dat je kunt inschrijven.

Je dient kennis te hebben van logica, verzamelingen en relaties. Je kunt:

- de syntactische eigenschappen van logische taal begrijpen en uitleggen en eenvoudige vertalingen maken tussen propositie- of predikaatlogische taal en natuurlijke taal,
- de geldigheid van formules of redeneringen in propositie- respectievelijk predikaatlogica onderzoeken,
- de belangrijkste verzamelingtheoretische begrippen uitleggen en eigenschappen van verzamelingen door middel van redeneringen en rekenregels aantonen,
- de axioma’s en Boole-algebra’s uitleggen en gebruiken, en abstracte Boole-algebra’s interpreteren in een concreet geval,
- de belangrijkste graaftheoretische begrippen uitleggen en over grafen redeneren,
- (simpele) wiskundige bewijzen formuleren, beweringen doen over wiskundige definities en heb je algemene wiskundige vaardigheden verworven.

Elke cursus heeft online en/of fysieke literatuur die na inschrijving voor de cursus beschikbaar wordt gesteld. Het fysieke materiaal wordt op jouw thuisadres geleverd. Literatuur hoeft dus niet afzonderlijk aangeschaft te worden.

Deze cursus heeft geen vast startmoment en kan zelfstandig bestudeerd worden. Wel wordt er begeleiding aangeboden in de periode februari tot juli.

Tijdens de bijeenkomsten of in de digitale leeromgeving kun je inhoudelijke vragen stellen aan de docenten. De online bijeenkomsten zijn in de avonduren en worden opgenomen; je kunt ze na afloop opnieuw bekijken.

Digitaal tentamen met open vragen (3 data per jaar).

Tentamens kunnen zowel thuis als op een studiecentrum afgelegd worden.

Bij de cursus wordt de volgende software gebruikt (niet verplicht): JFLAP, een visuele tool voor automaten, grammatica's en reguliere expressies.

De cursussen van de Open Universiteit volg je thuis wanneer jij tijd hebt (activerend online onderwijs met digitale begeleiding).

Meer informatie: www.ou.nl/studieaanbod/IB0802

Deze cursus is onderdeel van de premaster van de Master Computer Science en de Master Software Engineering bij de Open Universiteit. Voor uitgebreide informatie over deze masteropleiding zie: www.ou.nl/studieaanbod/macs of www.ou.nl/studieaanbod/mase

Voor vragen over eventuele toelating tot deze opleiding neem contact op met de studieadviseur via studieadvies.informatica@ou.nl.