Verschil tussen dubbelzinnige en eenduidige grammatica

De grootste verschil tussen dubbelzinnige en eenduidige grammatica is dat het dubbelzinnige grammatica is een contextvrije grammatica waarvoor een string bestaat die meer dan één meest linkse afleiding kan hebben, terwijl een eenduidige grammatica een contextvrije grammatica is waarvoor elke geldige string een uniek meest linkse afleiding heeft. 

Grammatica verwijst naar de syntactische regels in natuurlijke talen. In 1956 introduceerden computerwetenschappers een wiskundig model van grammatica voor het schrijven van computertaal. Als het mogelijk is om alle strings van een taal met behulp van een bepaalde grammatica af te leiden, wordt er gezegd dat de taal uit die grammatica wordt gegenereerd. Contextvrije grammatica is een type grammatica. Deze grammatica genereert contextvrije taal. De contextvrije grammatica kan ambigu of ondubbelzinnig zijn. Voor een bepaalde string, als er twee of meer afleidingen zijn, wordt die grammatica als onduidelijk beschouwd. Voor een bepaalde string, als er een enige unieke meest linkse afleiding is, wordt gezegd dat die grammatica ondubbelzinnige grammatica is.

Key Areas Covered

1. Wat is dubbelzinnige grammatica
     - Definitie, Voorbeeld
2. Wat is ondubbelzinnige grammatica
     - Definitie, Voorbeeld
3. Verschil tussen dubbelzinnige en eenduidige grammatica
     - Vergelijking van belangrijke verschillen

Sleutelbegrippen

Dubbelzinnige grammatica, eenduidige grammatica

Wat is dubbelzinnige grammatica

Een grammatica is dubbelzinnig als er twee of meer afleidingen voor een tekenreeks bestaan.

Figuur 1: Dubbelzinnige grammatica

Neem aan dat er een grammatica is die als volgt is gedefinieerd.

G = (S, a + b, +, *, P, S. De productievoorschriften zijn de volgende: S -> S + S | S * S | a | b Stel dat het verplicht is om genereer de String a + a * b.

Overweeg S -> S + S

Het vervangen van 'a' voor de meest linkse S geeft het volgende.

S-> a + S

Het substitueren van S * S voor S is als volgt.

S-> a + S * S 

Vervanging van 'a' voor de meest linkse S geeft de onderstaande uitvoer.

S -> a + a * S

Vervang 'b' voor de S geeft de volgende uitvoer.

S -> a + a * b

Dit is de vereiste tekenreeks om te genereren.

Bij gebruik van de andere productieregel, zal het geven

S -> S * S

Pas S + S toe op de meest linkse S en geef het volgende.

S -> S + S * S

Vervang 'a' voor meest linkse S,

S -> a + S * S

Vervang 'a' voor de meest linkse S,

S -> a + a * S

Vervang 'b' voor S geeft de volgende uitvoer.

S -> a + a * b

Nogmaals, het heeft de vereiste string gegenereerd. Daarom is er meer dan één afleiding om de tekenreeks te genereren. Daarom is het een ambigue grammatica.

Wat is ondubbelzinnige grammatica

In een ambigue grammatica heeft een bepaalde tekenreeks een unieke, meest linkse afleiding. Raadpleeg de volgende productieregels.

S -> L | a, L -> LS | S

Beschouw de S -> L-regel. Vervang LS in plaats van L.

S -> LS

Substituut S, voor eerste L.

S -> S S

Het vervangen van 'a' voor de meest linkse S geeft de onderstaande uitvoer.

S -> een S

Het vervangen van 'a' voor S geeft het volgende.

S -> a

Daarom heeft een string een unieke meest linkse afleiding. Het is dus een eenduidige grammatica.

Verschil tussen dubbelzinnige en eenduidige grammatica

Definitie

Een dubbelzinnige grammatica is een contextvrije grammatica waarvoor een reeks bestaat die meer dan één meest linkse afleiding of ontledingsbomen kan hebben. Ondubbelzinnige grammatica is een contextvrije grammatica waarvoor elke geldige string een unieke meest linkse afleiding of ontleedboom heeft.

Aantal meest linkse afleidingen

In dubbelzinnige grammatica kan een tekenreeks twee of meer meest linkse afleidingen hebben, maar in een ondubbelzinnige grammatica heeft een tekenreeks een unieke meest linkse afleiding.

Conclusie

Contextvrije grammatica kan ambigu of ondubbelzinnig zijn. Het verschil tussen dubbelzinnige en eenduidige grammatica is dat de dubbelzinnige grammatica een contextvrije grammatica is waarvoor een tekenreeks bestaat die meer dan één meest linkse afleiding kan hebben, terwijl een eenduidige grammatica een contextvrije grammatica is waarvoor elke geldige tekenreeks een uniek meest linkse afleiding heeft. 

Referentie:

1. "Dubbelzinnige grammatica." Wikipedia, Wikimedia Foundation, 17 juli 2018, hier beschikbaar.
2. "Compilerontwerp | Dubbelzinnige grammatica. "GeeksforGeeks, 10 feb. 2018, hier beschikbaar.
3. "Dubbelzinnige grammatica", Neso Academy, 29 maart 2017, hier beschikbaar.

Afbeelding met dank aan:

1. "Leftmostderivations jaredwf" door Jaredwf op Engelse Wikipedia - Overgezet van en.wikipedia naar Commons door EdwardHades (Public Domain) via Commons Wikimedia