Samenvatting Technologie van Moderne Informatiesystemen (HIRB) | 2025/26

Technologie van Moderne Informatiesystemen
Deel 1: Computationele en taalmodellen
1.1 Computationele Modellen
1. Inleiding formele talen
Formele talen: helpen om berekeningen, gedrag & taal uit te drukken
- Ze worden geproduceerd/gegenereerd door machines:
o Deze helpen om een abstractie te maken van een berekening
o Deze helpen ook om een abstractie te maken van taal zelf
- Compiler-theorie:
o Hoe code te analyseren en om te zetten in een werkbaar programma
o Kan gebruikt worden om fouten op te sporen in programma’s/code

Machine = abstract concept:
- Het heeft een grammatica/grammar en een alfabet/alphabet:
o Grammar: de regels die we gebruiken om een juiste syntax (zinsstructuur) te bekomen
o Alphabet: de (set van) symbolen/karakters/tokens (vaak door elkaar gebruikt) van de taal
- De machine ‘aanvaardt’ de taal die tot stand komt door de grammatica + alfabet
- Grammatica wordt uitgerdrukt in productieregels
o Capteren wat er kan geconstrueerd worden met de grammatica
o Bevat:
▪ Non-terminals: kunnen/moeten vervangen worden door andere symbolen
→ Uppercase (start symbool van een zin ‘S’, zelfstandige naamwoorden/nouns ‘N’, etc.)
▪ Terminals: eigenlijke symbolen van de taal (i.e. de elementen van het alfabet)
→ Lowercase
o Vorm van productieregels: 𝐴→𝑋
▪ 𝐴: non-terminal
▪ 𝑋: een reeks van terminal en/of non-terminal symbolen
▪ Betekenis: vervang ‘A’ door ‘X

Bv




Chomsky hiërarchie
- = manier om formele talen te structureren
- Hoe expressiever een (formele) taal, hoe complexer de
productieregels kunnen worden en hoe complexer de taal
- De recursief-enumereerbare talen zijn het meest complex
1

, ➔ Belang Chomsky:
o Helpen uitdrukken van computationale complexiteit:
→ Hoeveel instructies er nodig zijn in een bepaald algoritme/operatie/proces
o Compilatie van code:
▪ Compilers : converteren programmeercode naar machine-uitvoerbare code
▪ Grammars : om code te parsen (om te zetten in machinetaal) en analyseren de syntax
van programmeertalen
o Linguïstieke analyse (uiteraard) + wat kan een AI-taalmodel produceren
o Modelleren van systemen:
▪ Sommige systemen zijn makkelijk van opzet (bv. een koffiezet)
▪ sommige moeilijk (Netflix)
➔




2. Reguliere talen
Reguliere productieregels:
- Alle regels hebben maximaal 1 non-terminal symbool:
Ofwel aan het begin ofwel aan het einde van de rechterkant van de regel (na ->)
- Rechts-reguliere grammar = terminals staan altijd rechts
o A -> a
o A -> aB e = einde v/d sequentie/zin
o A -> e
- Links-reguliere grammar:
o A -> a
o B -> Ba
o A -> e
➔ Voorbeelden: (rechts regulier) →



Finite state machines = FSMs
- Accepteren/genereren een reguliere taal
- Worden veel gebruikt om simpele systemen te modelleren (e.g. zie AMMIS, 1MA)
- = Finite State Automata (FSAs)
- Formeel gezien is een FSM een tupel (Σ,𝑄,𝑞0,𝛿,𝐹):
o Σ = het alfabet
o 𝑄 = de eindige, niet-lege set van staten/states
o 𝑞0 ∈𝑄 = de beginstaat
o 𝛿: 𝑄 × Σ → 𝑄 = de transitiefunctie tussen staten
o 𝐹 ⊆𝑄 = de set van finale, ‘aanvaardbare’/‘accepting’ states

2

, - Voorbeeld
o Acdcda: accepted want:
▪ Eindigt in een accepting state (s3)
▪ Alle symbolen volgen op elkaar




Reguliere expressies = REs
- Algebraïsche notatie om een set van zinnen/strings te vatten
- O.a. Gebruikt in search strings (Word, Google Search, etc.)
- = RegExp
- Uitgevonden door Stephen Kleene bij het formaliseren van reguliere talen
- Twee standaarden met licht andere notatie:
o POSIX (hier gebruikt)
o Perl
- bv a (ab)* a = a + ab* + a → aabababa of aaba of …
[a-z] + [\.\?!] = 1 woord (lower case) + leesteken → battle! of bread? of green. of …

➔ uitgedrukt als FSM:
o [^a]*a[^a]*

o [a-ik-z]*[Jj]ohannes.*

FSM / RE problemen:
- Cijfers moeten snel hardgecodeerd worden
- Moeilijk grenzen aan te passen en bij te voegen
(alles is gevat in vaste staten)
- Kunnen niet tellen
- Kunnen niets onthouden
- Complexe condities niet modelleerbaar (onze oven heeft bepaalde temperaturen nodig)
- Parallelisme (volgorde staat niet vast) -> aantal staten ontploft snel
➔ FSM en RE wel goed voor:
o kleine, simpele systemen/bewerkingen vatten
o simpele taalregels uitdrukken

3. Context-vrije talen
Context-vrije talen:
- Zijn expressiever dan reguliere talen door een vorm van ingebouwd geheugen
- De vorm: 𝐴 →𝛼
o 𝐴 = een enkel, non-terminal symbool (zoals bij reguliere talen)
o 𝛼 = een zin/string van terminals en non-terminals (aantal en plaats maakt niet meer uit <>
reguliere talen)
- Voorbeeld formalismes:
o Pushdown automaten
o Petri nets (zonder uitbreidingen)
- Niet regulier: S -> aSa (S staat in het midden)  contextvrij


3

, - Voorbeeld:
o Regulier: S -> Sa
▪ S -> Sa -> Sba
-> Sbba
▪ S -> Sb -> Sabba
▪ S -> e -> abb
o Contextvrij:
S -> aSb
▪ S -> aSb -> aaSbb
▪ S -> e -> aaaSbbb
➔ de reguliere taal kan geen gelijk aantal a’s en b’s kan afdwingen
➔ de contextvrije regels kunnen dit wel door het gebruik van S tussen a en b
Pushdown automaten = PDAs
- Finite state machines met een stack als geheugen
- Formeel is een PDA een tupel (𝑄,Σ,Γ,𝛿,𝑞0,𝑍,𝐹) : (idem FSMs)
o Σ = het alphabet
o 𝑄 = de eindige, niet-lege set van staten/states
o Γ = het alfabet van de stack
o 𝑞0 ∈𝑄 = de beginstaat
o 𝑍∈Γ = het beginsymbool van de stack
o 𝛿:𝑄× ( Σ∪ {𝜖} ) × Γ → 𝑄 × Γ∗ = de transitiefunctie tussen staten
o 𝐹 ⊆𝑄 = de set van finale, ‘aanvaardbare’/‘accepting’ states
- Stack =
o Heeft maar 3 operaties:
▪ Read: leest het symbool aan de ‘top’ van de stack
▪ Push: voegt een symbool toe aan de top van de stack
▪ Pop: leest het top element en verwijdert het van de stack
o In PDA’s:
▪ Elke transitie tussen 2 staten kan pushen/poppen van de stack
▪ Vormt een rudimentaire vorm van geheugen
- Voorbeeld 1:




- Voorbeeld 2:




4