Skillnad mellan tvetydig och entydig grammatik

De huvudskillnad mellan tvetydig och entydig grammatik är att tvetydig grammatik är en kontextfri grammatik för vilken det finns en sträng som kan ha mer än en längst längsta avledning medan en entydig grammatik är en kontextfri grammatik för vilken varje giltig sträng har en unik vänstra längd. 

Grammatik hänvisar till de syntaktiska reglerna på naturliga språk. År 1956 introducerade datavetenskapare en matematisk modell av grammatik för att skriva datorspråk. Om det är möjligt att härleda alla strängar i ett språk med en viss grammatik, så sägs det att språket genereras av den grammatiken. Kontextfri grammatik är en typ av grammatik. Denna grammatik genererar kontextfritt språk. Kontextfri grammatik kan vara tvetydig eller entydig. För en viss sträng, om det finns två eller flera derivat, sägs den grammatiken vara tvetydig. För en viss sträng, om det finns en enda unik vänsterns avledning, sägs grammatiken vara otvetydig grammatik.

Viktiga områden som omfattas

1. Vad är tvetydig grammatik
     - Definition, exempel
2. Vad är otvetydig grammatik
     - Definition, exempel
3. Skillnad mellan tvetydig och entydig grammatik
     - Jämförelse av viktiga skillnader

Nyckelbegrepp

Tvetydig grammatik, entydig grammatik

Vad är tvetydig grammatik

En grammatik sägs vara tvetydig om det finns två eller flera derivat för en sträng.

Figur 1: Dubbelgrann grammatik

Antag att det finns en grammatik som definieras enligt följande.

G = (S, a + b, +, *, P, S. Produktionsreglerna är följande. S -> S + S | S * S | a | b. Antag att det är nödvändigt att generera strängen a + a * b.

Tänk på, S -> S + S

Att ersätta "a" för vänster mest S ger följande.

S-> a + S

Att ersätta S * S för S är som följer.

S-> a + S * S 

Genom att ersätta "a" till vänster kommer de flesta S att ge nedre utmatningen.

S -> a + a * S

Att ersätta "b" för S ger följande utmatning.

S -> a + a * b

Detta är den önskade strängen som ska genereras.

När du använder den andra produktionsregeln kommer den att ge

S -> S * S

Applicera S + S till vänster kommer de flesta S att ge följande.

S -> S + S * S

Ersättare 'a' för vänster mest S,

S -> a + S * S

Att ersätta "a" för vänster mest S,

S -> a + a * S

Att ersätta "b" för S ger följande utmatning.

S -> a + a * b

Återigen genererade den den önskade strängen. Därför finns det flera än en avledning för att generera strängen. Därför är det en tvetydig grammatik.

Vad är otvetydig grammatik

I en tvetydig grammatik har en viss sträng en unik vänstra avledning. Se följande produktionsregler.

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

Tänk på S -> L-regeln. Ersätt LS istället för L.

S -> LS

Suppleant S, för första L.

S -> S S

Att ersätta 'a' för vänster S kommer att ge nedgången nedan.

S -> a S

Att ersätta 'a' för S kommer att ge följande.

S -> a a

Därför har en sträng en unik vänstra avledning. Så det är en entydig grammatik.

Skillnad mellan tvetydig och entydig grammatik

Definition

En tvetydig grammatik är en kontextfri grammatik för vilken det finns en sträng som kan ha mer än en vänstra avledning eller tolkning av träd. Otvetydig grammatik är en kontextfri grammatik, för vilken varje giltig sträng har en unik längst längsta avledning eller parse-träd.

Antal vänstra avledningar

I tvetydig grammatik kan en sträng ha två eller flera vänstra derivat, men i otvetydig grammatik har en sträng en unik vänstra avledning.

Slutsats

Kontextfri grammatik kan vara tvetydig eller entydig. Skillnaden mellan tvetydig och otvetydig grammatik är att den tvetydiga grammatiken är en kontextfri grammatik för vilken det finns en sträng som kan ha mer än en längst längsta avledning medan en entydig grammatik är en kontextfri grammatik för vilken varje giltig sträng har en unik vänstra längd. 

Referens:

1. "Tvetydig grammatik." Wikipedia, Wikimedia Foundation, 17 juli 2018, Tillgänglig här.
2. "Compiler Design | Tvetydig grammatik. "GeeksforGeeks, 10 Feb. 2018, Tillgänglig här.
3. "Tvetydig grammatik", Neso-akademin, 29 mars 2017, Tillgänglig här.

Image Courtesy:

1. "Leftmostderivations jaredwf" Av Jaredwf på engelska Wikipedia - Överförd från en.wikipedia till Commons av EdwardHades (Public Domain) via Commons Wikimedia