Примеры полуколец из теории формального языка

Я изучаю алгебраическую теорию разбора. Моя первая проблема - это определение примеров полукольца, специфичных для теории формального языка. Вот попытка построить два примера.

1 При заданной грамматике CNF элементами полукольца являются наборы терминальных и нетерминальных символов с операциями:

i) Умножение , объединяющее два набора попарно в соответствии с правилом CYK. Например, учитывая грамматику CNF

s: p p | q r
t: p q
u: q q

тогда

$\{p,q,r\}\otimes \{p,r\} = \{s,t\}$

II) дополнение установлено объединение, например,

$\{p,q\}\oplus \{q,r\} = \{p,q,r\}$

К сожалению, умножение не ассоциативно.

2 Элементами второго полукольца являются наборы не символов, а правил грамматики [не обязательно в CNF], дополненных положением. Операции

i) Умножение , объединяющее все совпадающие пары элементов согласно полному правилу Эрли. Например, учитывая грамматику CNF

s: p q r 
r: s t | u

тогда

$\{s: p \bullet q r,s: p q \bullet r\}\otimes \{r: u \bullet \} = \{s: p q r \bullet \}$

II) Снова сложение объединения, например

$\{s: p \bullet q r, r: \bullet s t\}\oplus \{r: u \bullet \} = \{s: p \bullet q r, r: \bullet s t, r: u \bullet\}$

Этот пример также несовершенен.

Полукольцо с элементами, представляющими собой наборы грамматических правил, и умножение, являющееся подстановкой правил, кажется, работает нормально. Тем не менее, это просто замаскированная алгебра отношений. Действительно, давайте рассмотрим каждое грамматическое правило как класс эквивалентности - набор пар слов, состоящих из терминальных и нетерминальных букв, связанных с применением правила, например

$[t : s a] = \{ (t,sa),(ta,saa),(bt,bsa),(abt,absa),... \}$

Тогда распознавание слова в грамматике - это цепочка реляционных композиций, например

$[t:sa] \otimes [s:aa] \otimes \{(aaa,aaa)\} = \{(t,aaa)\}$

(Этот моном напоминает полином парсера полукольца из диссертации доктора философии Джоша Гудмана; однако, позвольте еще раз повторить, что построение новых полуколец с использованием полиномов и матриц здесь не представляет для нас интереса).

Итак, остается вопрос: является ли полукольцо формальных языков над алфавитом?$\Sigma$ единственный пример?

Есть много полуколец, связанных с теорией языка. Прежде всего, булево полукольцо. Далее, любой класс языков, замкнутый при конечном объединении и (конкатенации), является подполукольцом полукольца всех языков. Например, рациональные (= регулярные) языки образуют полукольцо. См. Также связанное понятие алгебры Клини .

$k \times k$матрицы над полукольцом образуют полукольцо. В частности, матрицы над булевым полукольцом кодируют недетерминированные конечные автоматы и матрицы над чуть большим полукольцом$\{-\infty, 0, 1\}$кодировать переходы автомата Бючи. Матрицы над полукольцами используются для характеристики рациональных рядов .

В тропических полукольцами , в частности ,$(\mathbb{N} \cup \{+\infty\}, \min, +)$ а также $(\mathbb{N} \cup \{-\infty\}, \max, +)$играть выдающуюся роль в теории автоматов. Они также привели к новому разделу математики, тропической геометрии .

Удовольствие от полуколец: функциональная жемчужина в злоупотреблении линейной алгеброй

Эффективный разбор контекстно-свободных языков Разделяй и властвуй

Я думаю, что вы можете придумать больше полуколец с правилами Эрли. Возьми прогноз. Вы можете сформировать бинарный оператор$S\otimes_{p,k} T = S \cup \bigcup (Y: \bullet \gamma$, k) $ такое, что объединение распространяется на все соответствующие правила. Затем алгоритм сначала вычисляет первое состояние Эрли, заданное как бесконечное, но в конечном итоге повторяющееся (настолько конечное) произведение в операторе:

$S(0) = \bigotimes_{p,0}^{\infty} S_0(0)$, Я не знаю, если это образует полукольцо с союзом, хотя. Может быть, это также формирует отношения с другими операциями.