Formele grammatica

Een formele grammatica is in de informatica en theoretische taalkunde een beschrijving van een formele taal, een verzameling strings (in deze context ook zinnen genoemd) in een bepaald alfabet. Er zijn twee categorieën te onderscheiden: de generatieve grammatica's die beschrijven hoe een string uit de taal gegenereerd kan worden, en de analytische grammatica's die beschrijven hoe men een string uit een taal kan herkennen (analyseren).

Een generatieve grammatica bestaat uit een verzameling van regels om strings te transformeren. Om een zin uit de taal te genereren begint men een zin die alleen bestaat uit een startsymbool en men past vervolgens regels toe (een willekeurig aantal keer, in elke mogelijke volgorde) om de zin te herschrijven. De formele taal bestaat uit alle zinnen die op deze manier gegenereerd kunnen worden. Elke mogelijke manier om regels toe te passen op de zin resulteert in een zin die behoort tot de taal. Als men een zin op meerdere manier kan genereren dan spreekt men van een ambigue grammatica.

Stel we hebben een alfabet met de letters $a$ en $b$, het startsymbool $S$ en de volgende regels:

1. $S\to aSb$

2. $S\to ba$

dan kunnen we met $S$ beginnen en een regel kiezen om toe te passen. Als we regel 1 kiezen dan verkrijgen we de zin $aSb$. Als we regel 1 opnieuw kiezen dan vervangen we $S$ door $aSb$ en we verkrijgen de zin $aaSbb$. Dit proces wordt herhaald totdat we alleen symbolen overhouden uit het alfabet (dus: $a$ en $b$). Als we nu regel 2 gebruiken dan vervangen we $S$ door $ba$ en we eindigen met de string aababb. We kunnen deze handelingen korter noteren met de volgende notatie: $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb$. De taal van de grammatica is de verzameling van alle zinnen (strings) die gegenereerd kunnen worden met dit proces: $\{ba,abab,aababb,aaababbb,...\}$.

Formele definitie

In de definitie van generatieve grammatica's zoals gegeven door Noam Chomsky in de jaren 50 bestaat een grammatica G uit de volgende componenten:

• een eindige verzameling $N$ van niet-terminale symbolen
• een eindige verzameling $\mathrm{\Sigma }$ van terminale symbolen, disjunct met $N$
• een eindige verzameling $P$ van productieregels, elk van de vorm:

$(\mathrm{\Sigma }\cup N{)}^{*}N(\mathrm{\Sigma }\cup N{)}^{*}\to (\mathrm{\Sigma }\cup N{)}^{*}$

waarbij ${}^{*}$ de Kleene-ster operator is en $\cup$ de vereniging van verzamelingen. Elke productieregel beeldt een string symbolen af op een andere string symbolen waarbij de eerste string ten minste 1 niet-terminaal symbool bevat. In het geval dat de tweede string de lege string is, noteert men vaak een epsilon ($ϵ$) om ambiguïteit te vermijden.

• een apart symbool $S\in N$, het startsymbool

Vaak wordt een grammatica G genoteerd als een viertupel $(N,\mathrm{\Sigma },P,S)$.

De taal van de formele grammatica $G=(N,\mathrm{\Sigma },P,S)$, genoteerd als $𝑳(G)$, wordt gedefinieerd als alle strings met symbolen uit $\mathrm{\Sigma }$ die gegenereerd kunnen worden vanuit het startsymbool $S$ door productieregels toe te passen uit $P$ tot er geen niet-terminale symbolen meer in de string aanwezig zijn.

Voorbeeld

We beschouwen de grammatica $G=(N,\mathrm{\Sigma },P,S)$ met $N=\{S,B\}$, $\mathrm{\Sigma }=\{a,b,c\}$, $S$ is het startsymbool en $P$ bevat de volgende productieregels:

1. $S\to aBSc$

2. $S\to abc$

3. $Ba\to aB$

4. $Bb\to bb$

Enkele voorbeelden van zinnen in $𝑳(G)$:

• $𝑺{\Rightarrow }_2𝒂𝒃𝒄$
• $𝑺{\Rightarrow }_1𝒂𝑩𝑺𝒄{\Rightarrow }_{2}aB𝒂𝒃𝒄c{\Rightarrow }_{3}a𝒂𝑩bcc{\Rightarrow }_{4}aa𝒃𝒃cc$
• $𝑺{\Rightarrow }_1𝒂𝑩𝑺𝒄{\Rightarrow }_{1}aB𝒂𝑩𝑺𝒄c{\Rightarrow }_{2}aBaB𝒂𝒃𝒄cc{\Rightarrow }_{3}a𝒂𝑩Babccc{\Rightarrow }_{3}aaB𝒂𝑩bccc$${\Rightarrow }_{3}aa𝒂𝑩Bbccc{\Rightarrow }_{4}aaaB𝒃𝒃ccc{\Rightarrow }_{4}aaa𝒃𝒃bccc$

Notatie: $L{\Rightarrow }_{i}R$ is te lezen als "$L$ genereert $R$ door toepassing van productieregel $i$". Het gegenereerde stuk wordt vet aangeduid.

Zie ook

• Generatieve taalkunde