Iloraz języka formalnego

W matematyce i informatyce właściwym ilorazem (lub po prostu ilorazem ) języka w odniesieniu do języka jest język składający się z ${1}}$ w takich , że $L_$ wx jest w ${\ displaystyle L_ {1}}$ dla jakiegoś łańcucha x w ${\ displaystyle L_ {2}}$ . Formalnie:

$${\ Displaystyle L_ {1} / L_ {2} = \ {w \ w \ Sigma ^ {*} \ środek \exists x\in L_{2}\dwukropek \ wx\in L_{1}\}}$$

$słowy$ , bierzemy wszystkie ciągi w $które$ mają sufiks w usuwamy ten

Podobnie, lewy iloraz z względem ${\ Displaystyle L_ {2}}$$to$ język składający się z łańcuchów w takich, że xw jest w $displaystyle L_ {1} }$ dla jakiegoś ciągu x w ${\ Displaystyle L_ {2}}$ . Formalnie:

$${\ Displaystyle L_ {2} \ ukośnik odwrotny L_ {1} = \ {w \ w \ Sigma ^ {*} \ środek \istnieje x\w L_{2}\dwukropek \ xw\w L_{1}\}}$$

Innymi słowy, bierzemy wszystkie ciągi w ${\ displaystyle L_ {1}}$ , które mają przedrostek w ${\ displaystyle L_ {2}}$ i usuwamy ten przedrostek.

$w$$,$$odwrotnej$ operandy kolejności: pierwszy operand to drugi a .

Przykład

Rozważać

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

I

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

Teraz, jeśli wstawimy dzielnik do elementu , część po prawej stronie jest w ${2}$$}$ tylko wtedy, gdy dzielnik jest umieszczony w sąsiedztwie b w takim przypadku i ≤ n i j = n ) lub sąsiadujące z a c (w takim przypadku i = 0 i j ≤ n ). Dlatego część po lewej stronie będzie albo $Displaystyle a ^ {n} b ^ {ni}}$${\ Displaystyle a ^ {n} b ^ {n} c ^ {nj}}$ lub za ; i można zapisać jako ${\ Displaystyle L_ {1} / L_ {2}}$

$${\ Displaystyle \ {\ a ^ {p} b ^ {q} c ^ {r} \ \ mid \ p = q \ geq r \ \ {\ tekst {lub}} \ \ (p \ geq q {\ tekst { i }}r=0)\ \}.}$$

Nieruchomości

Niektóre typowe właściwości zamknięcia operacji ilorazu obejmują:

• Iloraz języka regularnego z jakimkolwiek innym językiem jest regularny.
• Iloraz języka bezkontekstowego z językiem regularnym jest bezkontekstowy.
• Ilorazem dwóch języków bezkontekstowych może być dowolny rekurencyjnie wyliczalny język.
• Iloraz dwóch języków przeliczalnych rekurencyjnie jest przeliczalny rekurencyjnie.

Te właściwości domknięcia obowiązują zarówno dla lewego, jak i prawego ilorazu.

Zobacz też

• Pochodna Brzozowskiego