Den kontekstfri grammatik (CFG) for sproget `aⁿbⁿ`, hvor` n ≥ 0 ', er:

`` `

S -> ASB | ε

`` `

Forklaring:

* s: Dette er startsymbolet på grammatikken. Det repræsenterer en streng, der tilhører sproget `aⁿbⁿ`.

* a: Repræsenterer den bogstavelige karakter 'A'.

* b: Repræsenterer den bogstavelige karakter 'B'.

* |: Repræsenterer "eller". Det indikerer, at der er flere produktionsregler for symbolet til venstre.

* ε: Repræsenterer den tomme streng.

hvordan det fungerer:

1. `s -> asb`: Denne regel genererer en 'A', efterfulgt af en 'S' (som til sidst vil generere flere 'A'er og' B'er), efterfulgt af A 'B'. Hver gang denne regel anvendes, tilføjer den effektivt en 'A' til venstre og en 'B' til højre og opretholder den balance, der kræves af sproget.

2. `s -> ε`: Denne regel indeholder basissagen til rekursion. Det giver afledningen mulighed for at afslutte og producere den tomme streng (hvor n =0).

DERIVATION EKSEMPLER:

* n =0:tom streng (ε)

`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`

Hvorfor denne CFG genererer kun AⁿBⁿ:

Den eneste måde at udlede en streng fra 'S' er ved gentagne gange at anvende reglen 'S -> ASB' nul eller flere gange, efterfulgt af anvendelse af reglen 'S -> ε' en gang. Hver anvendelse af `s -> asb` tilføjer en 'a' til venstre og en 'b' til højre. Derfor vil den resulterende streng altid have et lige antal 'A'er og' B'er, med alle 'A's foregående alle' B'erne. Dette beskriver netop sproget `aⁿbⁿ`.

Nøglekoncepter:

* kontekstfri grammatik (CFG): En formel grammatik, hvor produktionsreglerne har et enkelt ikke-terminalt symbol på venstre side og enhver kombination af terminal- og ikke-terminale symboler på højre side. Anvendelsen af ​​en produktionsregel afhænger ikke af den kontekst, i hvilken det ikke-terminale symbol vises.

* terminalsymboler: Symboler, der vises i den endelige streng (f.eks. 'A', 'B').

* ikke-terminale symboler: Symboler, der repræsenterer grammatiske kategorier eller mellemtrin i afledningen (f.eks. 'S').

* Start symbol: Det ikke-terminale symbol, hvorfra alle strenge på sproget er afledt (f.eks. 'S').

* Produktionsregler: Regler, der specificerer, hvordan ikke -terminale symboler kan erstattes af andre symboler (f.eks. `S -> ASB`).

Denne CFG er et klassisk eksempel, der ofte bruges til at illustrere kraften i CFG'er og deres evne til at udtrykke sprog, der ikke er regelmæssige. Sproget `aⁿbⁿ` er et standardeksempel på et kontekstfrit sprog, der ikke er et almindeligt sprog.