| De contextvrije grammatica (CFG) voor de taal `aⁿbⁿ`, waarbij `n ≥ 0`, is:
```
S -> aSb | ε
```
Uitleg:
* S: Dit is het startsymbool van de grammatica. Het vertegenwoordigt een string die behoort tot de taal `aⁿbⁿ`.
* een: Vertegenwoordigt het letterlijke teken 'a'.
* b: Vertegenwoordigt het letterlijke teken 'b'.
* |: Vertegenwoordigt "of". Het geeft aan dat er meerdere productieregels zijn voor het symbool aan de linkerkant.
* ε: Vertegenwoordigt de lege tekenreeks.
Hoe het werkt:
1. `S -> aSb`: Deze regel genereert een 'a', gevolgd door een 'S' (die uiteindelijk meer 'a's en 'b's' zal genereren), gevolgd door een 'b'. Elke keer dat deze regel wordt toegepast, wordt er in feite één 'a' aan de linkerkant en één 'b' aan de rechterkant toegevoegd, waardoor het door de taal vereiste evenwicht behouden blijft.
2. `S -> ε`: Deze regel vormt het basisscenario voor de recursie. Hierdoor kan de afleiding eindigen, waardoor de lege string ontstaat (waarbij n =0).
Voorbeelden van afleidingen:
* n =0:lege tekenreeks (ε)
`S -> ε`
* n =1:"ab"
`S -> aSb`
`S -> aεb`
`S -> ab`
* n =2:"aabb"
`S -> aSb`
`S -> aaSbb`
`S -> aaεbb`
`S -> aabb`
* n =3:"aaabbb"
`S -> aSb`
`S -> aaSbb`
`S -> aaaSbbb`
`S -> aaaεbbb`
`S -> aaabbb`
Waarom deze CFG slechts aⁿbⁿ genereert:
De enige manier om een string af te leiden uit 'S' is door de regel `S -> aSb` herhaaldelijk nul of meer keren toe te passen, gevolgd door het één keer toepassen van de regel `S -> ε`. Elke toepassing van `S -> aSb` voegt één 'a' aan de linkerkant en één 'b' aan de rechterkant toe. Daarom zal de resulterende string altijd een gelijk aantal 'a's en 'b's hebben, waarbij alle 'a's voorafgaan aan alle 'b's. Dit beschrijft precies de taal `aⁿbⁿ`.
Belangrijkste concepten:
* Contextvrije grammatica (CFG): Een formele grammatica waarbij de productieregels één enkel niet-terminal symbool aan de linkerkant hebben en een combinatie van terminale en niet-terminale symbolen aan de rechterkant. De toepassing van een productieregel is niet afhankelijk van de context waarin het niet-terminale symbool verschijnt.
* Terminal-symbolen: Symbolen die in de laatste tekenreeks voorkomen (bijvoorbeeld 'a', 'b').
* Niet-terminale symbolen: Symbolen die grammaticale categorieën of tussenstappen in de afleiding vertegenwoordigen (bijvoorbeeld 'S').
* Startsymbool: Het niet-terminale symbool waarvan alle tekenreeksen in de taal zijn afgeleid (bijvoorbeeld 'S').
* Productieregels: Regels die specificeren hoe niet-terminale symbolen kunnen worden vervangen door andere symbolen (bijvoorbeeld `S -> aSb`).
Deze CFG is een klassiek voorbeeld dat vaak wordt gebruikt om de kracht van CFG's te illustreren en hun vermogen om talen uit te drukken die niet regulier zijn. De taal `aⁿbⁿ` is een standaardvoorbeeld van een contextvrije taal die geen reguliere taal is. |
