Den kontextfria grammatiken (CFG) för språket `aⁿbⁿ`, där` n ≥ 0` är:
`` `
S -> ASB | ε
`` `
Förklaring:
* s: Detta är startsymbolen för grammatiken. Det representerar en sträng som tillhör språket "aⁿbⁿ".
* A: Representerar den bokstavliga karaktären 'a'.
* B: Representerar den bokstavliga karaktären 'B'.
* |: Representerar "eller". Det indikerar att det finns flera produktionsregler för symbolen till vänster.
* ε: Representerar den tomma strängen.
Hur det fungerar:
1. `s -> asb`: Denna regel genererar en 'a', följt av en 's' (som så småningom kommer att generera mer 'A:er och' B), följt av en 'B'. Varje gång denna regel tillämpas lägger den effektivt till en 'a' till vänster och en 'b' till höger och upprätthåller balansen som krävs av språket.
2. `S -> ε`: Denna regel ger basfallet för rekursionen. Det tillåter härledningen att avsluta och producera den tomma strängen (där n =0).
derivatexempel:
* n =0:tom sträng (ε)
`S -> ε`
* n =1:"AB"
`S -> asb`
`S -> aεb`
`S -> ab`
* n =2:"aabb"
`S -> asb`
`S -> aasbb`
`S -> aaεbbB`
`S -> aabb`
* n =3:"AAABBB"
`S -> asb`
`S -> aasbb`
`S -> aaasbbb`
`S -> aaaεbbBB`
`S -> aaabbB`
Varför denna CFG genererar bara Aⁿbⁿ:
Det enda sättet att härleda en sträng från 's' är genom att upprepade gånger tillämpa regeln `s -> asb` noll eller fler gånger, följt av att tillämpa regeln` s -> ε 'en gång. Varje tillämpning av `s -> asb 'lägger till en' a 'till vänster och en' b 'till höger. Därför kommer den resulterande strängen alltid att ha ett lika antal 'A och' B, med alla 'A:s föregående alla' B:er. Detta beskriver exakt språket "aⁿbⁿ".
Nyckelkoncept:
* Kontextfri grammatik (CFG): En formell grammatik där produktionsreglerna har en enda icke-terminal symbol på vänster sida och varje kombination av terminala och icke-terminala symboler på höger sida. Tillämpningen av en produktionsregel beror inte på det sammanhang som den icke-terminala symbolen visas.
* terminalsymboler: Symboler som visas i den slutliga strängen (t.ex. 'a', 'b').
* icke-terminala symboler: Symboler som representerar grammatiska kategorier eller mellansteg i härledningen (t.ex. 's').
* Startsymbol: Den icke-terminala symbolen från vilken alla strängar på språket härstammar (t.ex. 's').
* Produktionsregler: Regler som anger hur icke -terminala symboler kan ersättas av andra symboler (t.ex. `s -> asb`).
Denna CFG är ett klassiskt exempel som ofta används för att illustrera kraften i CFG:er och deras förmåga att uttrycka språk som inte är regelbundna. Språket `aⁿbⁿ` är ett standard exempel på ett kontextfritt språk som inte är ett vanligt språk.
