Коэффициент формального языка - Quotient of a formal language - Wikipedia

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

${\displaystyle L_{1}/L_{2}=\{w\mid \exists x\colon \ x\in L_{2}\land wx\in L_{1}\}}$

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

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

${\displaystyle L_{2}\backslash L_{1}=\{w\mid \exists x\colon \ 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 a^{n}b^{n-i}}$ или же ${\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\ \}}$.

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

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

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

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

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

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

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

1. Линц, Питер (2011). Введение в формальные языки и автоматы. Издательство "Джонс и Бартлетт". С. 104–108. ISBN  9781449615529. Получено 7 июля 2014.