Грамматика глобального индекса

Грамматики глобального индекса (GIG) — это класс грамматик, представленный Кастаньо (2004). для моделирования ряда явлений, включая грамматику естественного языка и грамматику генома. Самое простое описание GIG — это сравнение с индексированными грамматиками . связан стек индексов В то время как в индексированных грамматиках с каждым нетерминальным символом и может варьироваться от одного к другому в зависимости от хода вывода, в GIG существует единый глобальный стек индексов, которым манипулируют в ходе деривации. деривация (которая является строго левой для любой операции перезаписи, которая помещает символ в стек). Из-за существования глобального стека деривация GIG считается завершенной, когда не осталось нетерминальных символов, подлежащих перезаписи, и стек пуст.

Описание правила

Правила GIG существуют в основном в четырех формах: правила, которые делают что-то безоговорочно, правила, которые делают что-то с условием самого верхнего символа стека, правила, которые помещают в стек, и правила, которые извлекают из стека. Мы можем обозначить их поочередно как:

$A\to \alpha$	(безоговорочно перепишите A как α , ничего не делая со стеком)
$A{\xrightarrow[{f}]{}}\alpha$	(перепишите A как α , если f — самый верхний символ стека, ничего не делая со стеком)
$A{\xrightarrow[{+f}]{}}x\alpha$	(безоговорочно перепишите A как xα и поместите f в стек)
$A{\xrightarrow[{-f}]{}}\alpha$	(условно перепишите A как α , если f — самый верхний символ стека, затем извлеките f из стека)

где f — любой индексный символ, α — любая строка терминалов и/или нетерминальных символов, а x — терминал является терминальным символом. Поскольку иногда правило перезаписи может быть обусловлено тем, что стек в некотором смысле пуст , символ # используется в качестве самого нижнего символа стека, что означает, что «пустой» стек содержит ровно один символ # .

Следует отметить третью форму правила — правило push, поскольку оно отличается от правила pop тем, что требует, чтобы все операции push вводили в строку вывода хотя бы один новый терминальный символ. Без этого ограничения класс грамматик был бы типом 0 и, следовательно, полным по Тьюрингу.

Пример

В этом примере мы будем обозначать шаги вывода, помещая строку вывода поверх стека, как в примере ${\frac {abXd}{[ffg]}}$.

GIG (но не trGIG, как показано ниже) могут генерировать неиндексированный язык. $\{ww^{+}:w\in \{a,b\}^{*}\}$ используя следующую грамматику:

$S\to AS~|~BS~|~C~|~\epsilon$

$C\to RC~|~L$

$R{\xrightarrow[{-f}]{}}RA$

$R{\xrightarrow[{-g}]{}}RB$

$R{\xrightarrow[{\#}]{}}\epsilon$

$A{\xrightarrow[{+f}]{}}a$

$B{\xrightarrow[{+g}]{}}b$

$L{\xrightarrow[{-f}]{}}La~|~a$

$L{\xrightarrow[{-g}]{}}Lb~|~b$

Вывод строки ababab следующий:

${\frac {S}{[\#]}}\to {\frac {AS}{[\#]}}\to {\frac {aS}{[\#f]}}\to {\frac {aBS}{[\#f]}}\to {\frac {abS}{[\#fg]}}\to {\frac {abC}{[\#fg]}}\to {\frac {abRC}{[\#fg]}}\to {\frac {abRBC}{[\#f]}}\to$

${\frac {abRABC}{[\#]}}\to {\frac {abABC}{[\#]}}\to {\frac {abaBC}{[\#f]}}\to {\frac {ababC}{[\#fg]}}\to {\frac {ababL}{[\#fg]}}\to {\frac {ababLb}{[\#f]}}\to {\frac {ababab}{[\#]}}$

Аналогичный вывод следует для отца , отца отца, отца отца и других подобных предложений.

Вычислительная мощность

Языки глобального индекса являются подмножеством контекстно-зависимых языков и расширенным набором контекстно-свободных языков. Известно, что GIG могут генерировать язык MIX/Bach. $\{p(a^{n}b^{n}c^{n}):n\geq 1\}$, где p — функция перестановки строк, которая, как предполагается (но не доказано), не может быть представлена ​​как индексированный язык. Неизвестно, все ли IG также являются GIG. Вполне возможно, что GIG и IG описывают просто перекрывающиеся подмножества CSL.

trGIGs

Подклассом GIG является класс trGIG, который делает правила pop и push единообразными, требуя, чтобы правила pop также вводили в вывод хотя бы один терминальный символ.

Пример

Пример такой грамматики, характеризующей язык $\{a^{m}b^{n}c^{m}d^{n}:m,n\geq 1\}$, является:

${\begin{array}{l}S\to AD\\A\to aAc~|~aBc\\B{\xrightarrow[{+f}]{}}bB~|~b\\D{\xrightarrow[{-f}]{}}dD~|~d\end{array}}$

Тогда вывод строки aabbbccddd будет следующим:

${\begin{aligned}{\frac {S}{[\#]}}&\to {\frac {AD}{[\#]}}\to {\frac {aAcD}{[\#]}}\to {\frac {aaBccD}{[\#]}}\to {\frac {aabBccD}{[\#f]}}\to {\frac {aabbBccD}{[\#ff]}}\\&\to {\frac {aabbbccD}{[\#fff]}}\to {\frac {aabbbccdD}{[\#ff]}}\to {\frac {aabbbccddD}{[\#f]}}\to {\frac {aabbbccddd}{[\#]}}\\\end{aligned}}$