Kvotient av ett formellt språk

Inom matematik och datavetenskap är den högra kvoten (eller helt enkelt kvoten ) för ett språk $L_{1}$ med avseende på språk $L_{2}$ språket som består av strängar w så att wx är i $L_{1}$ för någon sträng x i $L_{2}$ . Formellt:

$$L_{1}/L_{2}=\{w\in \Sigma ^{*}\mid \exists x\i L_{2}\colon \ wx\in L_{1}\}$$

Med andra ord tar vi alla strängar i $L_{1}$ som har ett suffix i $L_{2}$ , och tar bort detta suffix.

På liknande sätt är den vänstra kvotienten av $L_{1}$ med avseende på $L_{2}$ språket som består av strängar w så att xw är i $L_{1}$ för någon sträng x i $L_{2}$ . Formellt:

$$L_{2}\backslash L_{1}=\{w\in \Sigma ^{*}\ mitten \exists x\in L_{2}\colon \ xw\in L_{1}\}$$

Med andra ord tar vi alla strängar i $L_{1}$ som har ett prefix i $L_{2}$ , och tar bort detta prefix.

Observera att operanderna för $\backslash$ är i omvänd ordning: den första operanden är $L_{2}$ och $L_{1}$ är den andra.

Exempel

Överväga

$$L_{1}=\{a^{n}b^{n}c^{n}\mid n\geq 0\}$$

och

$$L_{2}=\{b^{i}c^{j}\mid i,j\geq 0\}.$$

Nu, om vi infogar en avdelare i ett element av $L_{1}$ , är delen till höger i $L_{2}$ endast om avdelaren är placerad intill ett b ( i vilket fall i ≤ n och j = n ) eller intill a c (i vilket fall i = 0 och j ≤ n ). Delen till vänster blir därför antingen $a^{n}b^{ni}$ eller $a^{n}b^ {n}c^{nj}$ ; och $L_{1}/L_{2}$ kan skrivas som

$$\{\ a^{p}b^{q}c^{r}\ \mid \ p=q\geq r\ \ {\text{eller}}\ \ (p\geq q{\text { och }}r=0)\ \}.$$

Egenskaper

Några vanliga stängningsegenskaper för kvotoperationen inkluderar:

• Kvoten för ett reguljärt språk med vilket annat språk som helst är regelbunden.
• Kvoten av ett kontextfritt språk med ett reguljärt språk är kontextfritt.
• Kvoten av två kontextfria språk kan vara vilket som helst rekursivt uppräknat språk.
• Kvoten av två rekursivt uppräknade språk är rekursivt uppräknade.

Dessa stängningsegenskaper gäller för både vänster och höger kvot.

Se även

• Brzozowski-derivat