Частное формального языка - Википедия - Quotient of a formal language

В математика и Информатика, то правое частное (или просто частное) из язык ${ displaystyle L_ {1}}$ относительно языка ${ displaystyle L_ {2}}$ это язык, состоящий из струны ш такой, что wx в ${ displaystyle L_ {1}}$ для какой-то строки Икс в ${ displaystyle L_ {2}}$.^[1] Формально:

${ Displaystyle L_ {1} / L_ {2} = {ш середина существует х двоеточие х в L_ {2} земля wx в L_ {1} }}$

Другими словами, мы берем все струны в ${ displaystyle L_ {1}}$ которые имеют суффикс в ${ displaystyle L_ {2}}$, и удалите этот суффикс.

Точно так же левое частное из ${ displaystyle L_ {1}}$ относительно ${ displaystyle L_ {2}}$ это язык, состоящий из строк ш такой, что xw в ${ displaystyle L_ {1}}$ для какой-то строки Икс в ${ displaystyle L_ {2}}$. Формально:

${ Displaystyle L_ {2} обратная косая черта L_ {1} = {w mid exists x двоеточие x in L_ {2} land xw in L_ {1} }}$

Другими словами, мы берем все струны в ${ displaystyle L_ {1}}$ которые имеют префикс в ${ displaystyle L_ {2}}$, и удалите этот префикс.

Обратите внимание, что операнды ${ displaystyle backslash}$ в обратном порядке: первый операнд ${ displaystyle L_ {2}}$ и ${ displaystyle L_ {1}}$ второй.

Пример

Учитывать

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

и

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

Теперь, если мы вставим разделитель в элемент ${ displaystyle L_ {1}}$, часть справа находится в ${ displaystyle L_ {2}}$ только если разделитель расположен рядом с б (в таком случае я ≤ п и j = п) или рядом с c (в таком случае я = 0 и j ≤ п). Следовательно, левая часть будет либо ${ Displaystyle а ^ {п} Ь ^ {п-я}}$ или же ${ displaystyle a ^ {n} b ^ {n} c ^ {n-j}}$; и ${ Displaystyle L_ {1} / L_ {2}}$ можно записать как

${ Displaystyle { a ^ {p} b ^ {q} c ^ {r} mid p = q geq r lor p geq q land r = 0 }}$.

Характеристики

Некоторые общие свойства замыкания операции частного включают:

• Частное от обычный язык с любым другим языком является обычным.
• Частное от контекстно свободный язык с обычным языком контекстно-свободный.
• Отношение двух контекстно-свободных языков может быть любым. рекурсивно перечислимый язык.
• Фактор двух рекурсивно перечислимых языков рекурсивно перечислим.

Эти свойства замыкания сохраняются как для левого, так и для правого частного.

Смотрите также

• Производная Бжозовского

Рекомендации