附标语言

下列语言是有附标的，但不是上下文无关的:

${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n\geq 1\}}$  ^[3]

${\displaystyle \{a^{n}b^{m}c^{n}d^{m}|m,n\geq 0\}}$  ^[2]

下面两个语言也是有附标的，但不是 Gazdar 所特征化的适度上下文有关语言:

${\displaystyle \{a^{2^{n}}|n\geq 0\}}$  ^[2]

${\displaystyle \{www|w\in \{a,b\}^{+}\}}$  ^[3]

在另一方面，下列语言不是有附标的 ^[4]:

${\displaystyle \{(ab^{n})^{n}|n\geq 0\}}$ 

• 乔姆斯基层级
• 附标文法
• 适度上下有关文法

1. ^ Aho, Alfred. Indexed grammars—an extension of context-free grammars. Journal of the ACM. 1968, 15 (4): 647–671 [2007-10-19]. ISSN 0004-5411. （原始内容存档于2019-07-13）. 
2. ^ ^{2.0 2.1 2.2} Partee, Barbara; Alice ter Meulen, and Robert E. Wall. Mathematical Methods in Linguistics. Kluwer Academic Publishers. 1990: 536–542. ISBN 978-90-277-2245-4.  引文使用过时参数coauthors (帮助)
3. ^ ^{3.0 3.1 3.2} Gazdar, Gerald. Applicability of Indexed Grammars to Natural Languages. U. Reyle and C. Rohrer (编). Natural Language Parsing and Linguistic Theories. 1988: 69-94. 
4. ^ Gilman, Robert. A shrinking lemma for indexed languages. Theoretical Computer Science. 1996, 163 (1-2): 277–281. 

• "NLP in Prolog" chapter on indexed grammars and languages