Частное формального языка

В математике и информатике правильное частное (или просто частное ) языка . $L_{1}$ что касается языка $L_{2}$ — это язык, состоящий из строк w таких, что wx находится в $L_{1}$ для некоторой строки x в $L_{2}$. Формально: $$L_{1}/L_{2}=\{w\in \Sigma ^{*}\mid \exists x\in L_{2}\colon \ wx\in L_{1}\}$$

Другими словами, для всех строк в $L_{1}$ у которых есть суффикс $L_{2}$, суффикс удаляется.

Аналогично, левое частное $L_{1}$ относительно $L_{2}$ — это язык, состоящий из строк w таких, что xw находится в $L_{1}$ для некоторой строки x в $L_{2}$. Формально: $$L_{2}\backslash L_{1}=\{w\in \Sigma ^{*}\mid \exists x\in L_{2}\colon \ xw\in L_{1}\}$$

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

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

Пример

Учитывать $$L_{1}=\{a^{n}b^{n}c^{n}\mid n\geq 0\}$$и $$L_{2}=\{b^{i}c^{j}\mid i,j\geq 0\}.$$

Теперь, если мы вставим разделитель в элемент $L_{1}$, часть справа находится в $L_{2}$ только если разделитель расположен рядом с b (в этом случае i ≤ n и j = n ) или рядом с c (в этом случае i = 0 и j ≤ n ). Следовательно, часть слева будет либо $a^{n}b^{n-i}$ или $a^{n}b^{n}c^{n-j}$; и $L_{1}/L_{2}$ можно записать как $$\{\ a^{p}b^{q}c^{r}\ \mid \ p=q\geq r\ \ {\text{or}}\ \ (p\geq q{\text{ and }}r=0)\ \}.$$

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

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

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

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

См. также

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