Индексированная грамматика

Индексированные грамматики — это обобщение контекстно-свободных грамматик , в котором нетерминалы снабжены списками флагов или индексных символов . Язык, созданный с помощью индексированной грамматики, называется индексированным языком .

Определение [ править ]

определение Хопкрофта и . Ульмана Современное

В современных публикациях после Хопкрофта и Ульмана (1979): ^[2] индексированная грамматика формально определяется как набор из 5 G = ⟨ N , T , F , P , S ⟩ где

N — набор переменных или нетерминальных символов ,
T — набор (« алфавит ») терминальных символов,
F — это набор так называемых индексных символов , или индексов ,
S ∈ N — начальный символ , а
P — конечное множество продукций .

В постановках, а также при выводе индексированных грамматик строка («стек») σ ∈ F ^* индексных символов прикреплен к каждому нетерминальному символу A ∈ N , обозначенному A [ σ ]. ^{[примечание 1]}За терминальными символами не могут следовать стеки индексов. Для индексного стека σ ∈ F ^* и строка α ∈ ( N ∪ T ) ^*из нетерминальных и терминальных символов α [ σ ] обозначает результат присоединения [ σ ] к каждому нетерминалу в α ; например, если равно BC $d с E [α$ терминальными символами a , d ∈ T и $B, C, E нетерминальными N$ символами, то [ σ ] B $[обозначает σ] C E σ] d [σ α] .$ Используя эти обозначения, каждое производство в P должно иметь вид

А [σ] → α[σ],
A [σ] → B [ f σ], или
А [ ж σ] → а[σ],

где A , B ∈ N — нетерминальные символы, f ∈ F — индекс, σ ∈ F ^* является строкой индексных символов, а α ∈ ( N ∪ T ) ^*представляет собой строку нетерминальных и терминальных символов. Некоторые авторы пишут «..» вместо « σ » для стека индексов в производственных правилах; правило типа 1, 2 и 3 тогда читается как $A [..]\to α [..], A [..] \to B [f ..]$ и $A [f ..] \to α [..]$ , соответственно.

Выводы аналогичны выводам в контекстно-свободной грамматике, за исключением стека индексов, прикрепленного к каждому нетерминальному символу. Когда применяется такая продукция, как, например, A [ σ ] → B [ σ ] C [ σ ], стек индексов A копируется как в B , так и в C . Более того, правило может помещать индексный символ в стек или извлекать его «самый верхний» (т. е. самый левый) индексный символ.

Формально отношение ⇒ («прямой вывод») определено на множестве ( N [ F ^*]∪ T ) ^* «форм предложения» следующим образом:

Если A [ σ ] → α [ σ ] является продукцией типа 1, то β A [ φ ] γ ⇒ β α [ φ ] γ , используя приведенное выше определение. левой части правила То есть стек индексов φ копируется в каждый нетерминал правой части.
Если A [ σ ] → B [ fσ ] — продукция типа 2, то β A [ φ ] γ ⇒ β B [ fφ ] γ . То есть стек индексов правой стороны получается из стека φ левой стороны путем помещения в него f .
Если A [ fσ ] → α [ σ ] является продукцией типа 3, то β A [ fφ ] γ ⇒ β α [ φ ] γ , снова используя определение α [ σ ]. То есть первый индекс f извлекается из стека левой части, который затем распределяется по каждому нетерминалу правой части.

Как обычно, отношение вывода ∗ ⇒ определяется как рефлексивное транзитивное замыкание прямого вывода ⇒. Язык L ( G ) = { w ∈ T ^*: S ∗ ⇒ w } — множество всех строк терминальных символов, выводимых из начального символа.

Исходное определение Ахо [ править ]

Исторически концепция индексированных грамматик была впервые введена Альфредом Ахо (1968). ^[3]используя другой формализм. Ахо определил индексированную грамматику как кортеж из 5 ( N , T , F , P , S ), где

N — конечный алфавит переменных или нетерминальных символов.
T — конечный алфавит терминальных символов.
Ф ⊆ 2 ^{Н × ( Н ∪ Т ) ^*} — это конечное множество так называемых флагов (каждый флаг сам по себе является набором так называемых индексных продукций )
P ⊆ N × ( NF ^* ∪ Т ) ^* это конечное множество продукций
S ∈ N — начальный символ

Прямые выводы заключались в следующем:

Продукция p = ( A → X ₁ η ₁ … X _k η _k ) из P соответствует нетерминалу A ∈ N , за которым следует его (возможно, пустая) строка флагов ζ ∈ F ^*. В контексте γ Aζ δ через p приводит к γ X ₁ θ ₁ … X _k θ _k δ , где θ _i = η _i ζ , если X _i было нетерминалом, и пустым словом в противном случае. старые флаги A Поэтому копируются в каждый новый нетерминал, созданный p . Каждое такое производство можно смоделировать соответствующими производствами типа 1 и 2 в формализме Хопкрофта-Ульмана.
Произведение индекса p = ( A → X ₁ … X _k ) ∈ f соответствует Afζ (флаг f , из которого он исходит, должен соответствовать первому символу, следующему за нетерминалом A ), и копирует оставшуюся индексную строку ζ в каждый новый нетерминал: γ Afζ δ выводится в γ X ₁ θ ₁ … X _k θ _k δ , где θ _i — пустое слово, когда X _i является терминалом, и ζ , когда оно нетерминалом. Каждое такое производство соответствует производству типа 3 в формализме Хопкрофта-Ульмана.

Этот формализм, например, используется Хаяси (1973, стр. 65-66). ^[4]

Примеры [ править ]

На практике стопки индексов могут подсчитывать и запоминать, какие правила применялись и в каком порядке. Например, индексированные грамматики могут описывать контекстно-зависимый язык троек слов { www : w ∈ { a , b } ^* }:

С [ σ ]	→	С [ fσ ]	Т [ fσ ]	→	а Т [ σ ]
С [ σ ]	→	S [ gσ ]	Т [ гσ ]	→	бТ ] [ σ
С [ σ ]	→	Т [ с ] Т [ с ] Т [ с ]	Т []	→	е

Тогда производным от abbabbabb будет

S []

⇒

S [г]

⇒

S [гг]

⇒

S [fgg]

⇒

T [fgg] T [fgg] T [fgg]

⇒

a T [gg] T [fgg] T [fgg]

⇒

ab T [g] T [fgg] T [fgg]

⇒

abb T [] T [fgg] T [fgg]

⇒

abb T [fgg] T [fgg]

⇒

...

⇒

abb abb T [fgg]

⇒

...

⇒

abb abb абб

.

В качестве другого примера, грамматика G = ⟨ { S , T , A , B , C }, { a , b , c }, { f , g }, P , S ⟩ порождает язык { a ^нб ^нс ^н: n ≥ 1 }, где производственный набор P состоит из

S [ σ ] → Т [ gσ ]	А [ fσ ] → а А [ σ ]	А [ gσ ] → а
Т [ σ ] → Т [ fσ ]	B [ fσ ] → б B [ σ ]	Б [ гσ ] → б
Т [ σ ] → А [ σ ] B [ σ ] C [ σ ]	C [ fσ ] → c C [ σ ]	C [ gσ ] → c

Пример вывода:

S []

⇒

T [g]

⇒

T [fg]

⇒

A [fg] B [fg] C [fg]

⇒

aA [g] B [fg] C [fg]

⇒

aA [g] bB [g] C [fg]

⇒

aA [g] bB [g] cC [g]

⇒

aa bB [g] cC [g]

⇒

aa bb cC [g]

⇒

aa bb cc

.

Оба примера языка не являются контекстно-свободными по лемме о накачке .

Свойства [ править ]

Хопкрофт и Ульман склонны рассматривать индексированные языки как «естественный» класс, поскольку они порождены несколькими формализмами, отличными от индексированных грамматик, а именно. ^[5]

Ахо Односторонний вложенный стек-автомат ^[6]
Фишера Макрограмматики ^[7]
Автоматы Грайбаха со стопками стопок ^[8]
Майбаума Алгебраическая характеристика ^[9]

Хаяши ^[4]обобщил лемму о накачке на индексированные грамматики. И наоборот, Гилман ^[10]^[11] дает «лемму о сокращении» для индексируемых языков.

Линейные индексированные грамматики [ править ]

Джеральд Газдар определил второй класс — линейные индексированные грамматики ( LIG ). ^[14] требуя, чтобы не более одного нетерминала в каждом производстве было указано как получатель стека, ^{[заметка 2]}тогда как в обычной индексированной грамматике все нетерминалы получают копии стека. Формально линейная индексированная грамматика определяется аналогично обычной индексированной грамматике, но требования к форме продукции изменяются следующим образом:

А [ σ ] → α [] B [ σ ] β [],
А [ σ ] → α [] B [ fσ ] β [],
А [ fσ ] → α [] B [ σ ] β [],

где A , B , f , σ , α используются, как указано выше , и β ∈ ( N ∪ T ) ^* представляет собой строку нетерминальных и терминальных символов, таких как α . ^{[заметка 3]}Кроме того, отношение прямого вывода ⇒ определяется аналогично приведенному выше. Этот новый класс грамматик определяет строго меньший класс языков. ^[15] который принадлежит к умеренно контекстно-зависимым классам.

Язык { www : w ∈ { a , b } ^* } порождается индексированной грамматикой, но не линейной индексированной грамматикой, в то время как { ww : w ∈ { a , b } ^* } и { а ^н б ^н с ^н : n ≥ 1 } порождаются линейной индексированной грамматикой.

Если допускаются как исходные, так и измененные правила производства, языковой класс остается индексированным языком. ^[16]

Пример [ править ]

Обозначая σ произвольную последовательность символов стека, мы можем определить грамматику языка L = { a ^н б ^н с ^н| п ≥ 1 } ^{[примечание 4]} как

С [ σ ]	→	а S [ fσ ] c
С [ σ ]	→	Т [ с ]
Т [ fσ ]	→	Т [ п ] б
Т []	→	е

Чтобы получить строку abc, нам нужно выполнить следующие действия:

S [] ⇒ aS [ f ] c ⇒ aT [ f ] c ⇒ aT [] bc ⇒ abc

Сходным образом:

S [] ⇒ aS [ f ] c ⇒ aaS [ ff ] cc ⇒ aaT [ ff ] cc ⇒ aaT [ f ] bcc ⇒ aaT [] bbcc ⇒ aabbcc

Вычислительная мощность [ править ]

Языки с линейной индексацией являются подмножеством индексированных языков, и, таким образом, все LIG могут быть перекодированы как IG, что делает LIG менее мощными, чем IG. Преобразование из LIG в IG относительно простое. ^[17] Правила LIG в целом выглядят примерно так $X[\sigma ]\to \alpha Y[\sigma ]\beta$ , по модулю push/pop части правила перезаписи. Символы $\alpha$ и $\beta$ представляют строки терминальных и/или нетерминальных символов, и любой нетерминальный символ в любом из них должен иметь пустой стек по определению LIG. Это, конечно, противоречит тому, как определяются IG: в IG нетерминалы, чьи стеки не передаются или не извлекаются, должны иметь точно такой же стек, что и переписанный нетерминал. Таким образом, каким-то образом нам нужно иметь нетерминалы в $\alpha$ и $\beta$ которые, несмотря на наличие непустых стопок, ведут себя так, как если бы у них были пустые стопки.

Рассмотрим правило $X[\sigma ]\to Y[]Z[\sigma f]$ как примерный случай. При преобразовании этого в IG замена $Y[]$ должно быть какое-то $Y^{\prime }[\sigma ]$ это ведет себя точно так же, как $Y[]$ независимо от того, что $\sigma$ является. Чтобы добиться этого, мы можем просто иметь пару правил, которые принимают любые $Y^{\prime }[\sigma ]$ где $\sigma$ не пуст и извлекает символы из стека. Затем, когда стек пуст, его можно переписать как $Y[]$ .

Y^{\prime }[\sigma f]\to Y^{\prime }[\sigma ]

Y^{\prime }[]\to Y[]

Мы можем применить это в целом, чтобы получить IG из LIG. Например, если LIG для языка $\{a^{n}b^{n}c^{n}d^{m}|n\geq 1,m\geq 1\}$ как следует:

S[\sigma ]\to T[\sigma ]V[]

V[]\to d~|~dV[]

T[\sigma ]\to aT[\sigma f]c~|~U[\sigma ]

U[\sigma f]\to bU[\sigma ]

U[]\to \epsilon

Предложенное правило здесь не является правилом IG, но, используя приведенный выше алгоритм преобразования, мы можем определить новые правила для $V^{\prime }$ , изменив грамматику на:

S[\sigma ]\to T[\sigma ]V^{\prime }[\sigma ]

V^{\prime }[\sigma f]\to V^{\prime }[\sigma ]

V^{\prime }[]\to V[]

V[]\to d~|~dV[]

T[\sigma ]\to aT[\sigma f]c~|~U[\sigma ]

U[\sigma f]\to bU[\sigma ]

U[]\to \epsilon

Каждое правило теперь соответствует определению IG, в котором все нетерминалы в правой части правила перезаписи получают копию стека переписанного символа. Таким образом, индексированные грамматики способны описывать все языки, которые могут описывать линейно индексированные грамматики.

другими формализмами Связь с

Виджай-Шанкер и Вейр (1994) ^[18]демонстрирует, что линейные индексированные грамматики, комбинаторные категориальные грамматики , древовидные грамматики и головные грамматики определяют один и тот же класс строковых языков. Их формальное определение линейных индексированных грамматик ^[19] отличается от вышеперечисленного . ^{[ нужны разъяснения ]}

LIG (и их слабо эквиваленты ) строго менее выразительны (то есть они генерируют правильное подмножество), чем языки, созданные другим семейством слабо эквивалентного формализма, в которое входят: LCFRS , MCTAG , MCFG и минималистские грамматики (MG). Последнее семейство также можно проанализировать за полиномиальное время . ^[20]

Грамматики распределенного индекса [ править ]

Другая форма индексированных грамматик, представленная Штаудахером (1993), ^[12]— это класс грамматик распределенного индекса (DIG). Что отличает DIG от индексированных грамматик Ахо, так это распространение индексов. В отличие от IG Ахо, которые распределяют весь стек символов по всем нетерминалам во время операции перезаписи, DIG делят стек на подстеки и распределяют подстеки по выбранным нетерминалам.

Общая схема правил для правила двоичного распределения DIG имеет вид

X[f₁...f_if_i+1...f_n] → α Y[f₁...f_i] β Z[f_i+1...f_n[

Где α, β и γ — произвольные терминальные строки. Для троичной распределяющей строки:

[ f₁...f_if_i+1...f_jf_j+1...f_n] → α Y[f₁...f_i] β Z[f_i+1...f _j ] γ W [ f _{j +1} ... f _n ] η

И так далее для большего количества нетерминалов в правой части правила перезаписи. В общем, если в правой части правила перезаписи находится m нетерминалов, стек разделяется m способами и распределяется между новыми нетерминалами. Обратите внимание, что существует особый случай, когда раздел пуст, что фактически делает правило правилом LIG. Таким образом, языки с распределенным индексом являются расширенным набором языков с линейной индексацией.

См. также [ править ]

Иерархия Хомского

Примечания [ править ]

^ «[» и «]» — метасимволы, обозначающие стек.
^ все остальные нетерминалы получают пустой стек
^ Перейти обратно: ^а ^б Чтобы вообще сгенерировать какую-либо строку, необходимо признать, что некоторые произведения не имеют нетерминального символа в правой части. Однако Газдар не стал обсуждать этот вопрос.
^ См. правильно проиндексированная грамматика для того же языка, указанная выше . Последнее правило, т. T []→ε линейной индексированной грамматики не соответствует определению Газдара в строгом смысле, ср. ^{[заметка 3]}

Ссылки [ править ]

^ Перейти обратно: ^а ^б Хопкрофт, Джон Э .; Джеффри Д. Уллман (1979). Введение в теорию автоматов, языки и вычисления . Аддисон-Уэсли. ISBN 978-0-201-02988-8 .
^ Хопкрофт и Ульман (1979), ^[1]Разд.14.3, стр.389-390. Этот раздел опущен во 2-м издании 2003 г.
^ Ахо, Альфред (1968). «Индексированные грамматики — расширение контекстно-свободных грамматик» . Журнал АКМ . 15 (4): 647–671. дои : 10.1145/321479.321488 . S2CID 9539666 .
^ Перейти обратно: ^а ^б Хаяси, Такеши (1973). «О деревьях вывода индексированных грамматик: расширение uvwxy - теоремы» . Публикации НИИ математических наук . 9 : 61–92. дои : 10.2977/prims/1195192738 .
^ Хопкрофт и Ульман (1979), ^[1] Библиографические примечания, стр.394-395.
^ Альфред Ахо (1969). «Вложенные стековые автоматы» . Журнал АКМ . 16 (3): 383–406. дои : 10.1145/321526.321529 . S2CID 685569 .
^ Майкл Дж. Фишер (1968). «Грамматики с макроподобными произведениями». Учеб. 9-я Энн. IEEE симп. по теории коммутации и автоматов (SWAT) . стр. 131–142. дои : 10.1109/SWAT.1968.12 .
^ Шейла А. Грейбах (1970). «Полные AFL и вложенная итерационная замена» . Информация и контроль . 16 (1): 7–35. дои : 10.1016/s0019-9958(70)80039-0 .
^ ЦЭ Майбаум (1974). «Обобщенный подход к формальным языкам» . Журнал компьютерных и системных наук . 8 (3): 409–439. дои : 10.1016/s0022-0000(74)80031-0 .
^ Роберт Х. Гилман (1996). «Сжимающая лемма для индексируемых языков». Теоретическая информатика . 163 (1–2): 277–281. arXiv : математика/9509205 . дои : 10.1016/0304-3975(96)00244-7 . S2CID 14479068 .
^ Роберт Х. Гилман (сентябрь 1995 г.). «Сжимающая лемма для индексируемых языков». arXiv : математика/9509205 .
^ Перейти обратно: ^а ^б Штаудахер, Питер (1993), «Новые рубежи за пределами контекстной свободы: DI-грамматики (DIG) и DI-автоматы». (PDF) , Шестая конференция Европейского отделения Ассоциации компьютерной лингвистики (EACL '93) , стр. 358–367.
^ Дэвид Дж. Вейр; Аравинд К. Джоши (1988). «Комбинаторные категориальные грамматики: порождающая сила и связь с линейными системами контекстно-свободного переписывания» (PDF) . Учеб. 26-е заседание доц. Вычислить. Линг . стр. 278–285.
^ Согласно Штаудахеру (1993, стр.361 слева, раздел 2.2), ^[12] название «линейные индексированные грамматики» не использовалось в статье Газдара 1988 года, но появилось позже, например, в Weir and Joshi (1988). ^[13]
^ Газдар, Джеральд (1988). «Применимость индексированных грамматик к естественным языкам». В У. Рейле и К. Рорере (ред.). Анализ естественного языка и лингвистические теории . Исследования в области лингвистики и философии. Том. 35. Издательство Д. Рейделя. стр. 69–94. ISBN 978-1-55608-055-5 .
^ Газдар (1988), Приложение, стр.89.
^ Газдар 1988, Приложение, стр.89-91.
^ Виджай-Шанкер, К.; Вейр, Дэвид Дж. 1994. (1994). «Эквивалентность четырех расширений контекстно-свободных грамматик» . Теория математических систем . 27 (6): 511–546. дои : 10.1007/bf01191624 . S2CID 12336597 . {{cite journal}}: CS1 maint: числовые имена: список авторов ( ссылка )
^ стр.517-518
^ Йохан ФАК ван Бентем; Алиса тер Меулен (2010). Справочник по логике и языку (2-е изд.). Эльзевир. п. 404. ИСБН 978-0-444-53727-0 .

Внешние ссылки [ править ]

Глава «НЛП в Прологе», посвященная индексированным грамматикам и языкам.

[3] «[» и «]» — метасимволы, обозначающие стек.

[16] все остальные нетерминалы получают пустой стек

[Gazdars_def-17] Перейти обратно: ^а ^б Чтобы вообще сгенерировать какую-либо строку, необходимо признать, что некоторые произведения не имеют нетерминального символа в правой части. Однако Газдар не стал обсуждать этот вопрос.

[20] См. правильно проиндексированная грамматика для того же языка, указанная выше . Последнее правило, т. T []→ε линейной индексированной грамматики не соответствует определению Газдара в строгом смысле, ср. ^{[заметка 3]}

[Hopcroft_and_Ullman-1] Перейти обратно: ^а ^б Хопкрофт, Джон Э .; Джеффри Д. Уллман (1979). Введение в теорию автоматов, языки и вычисления . Аддисон-Уэсли. ISBN 978-0-201-02988-8 .

[2] Хопкрофт и Ульман (1979), ^[1]Разд.14.3, стр.389-390. Этот раздел опущен во 2-м издании 2003 г.

[aho1968-4] Ахо, Альфред (1968). «Индексированные грамматики — расширение контекстно-свободных грамматик» . Журнал АКМ . 15 (4): 647–671. дои : 10.1145/321479.321488 . S2CID 9539666 .

[Hayashi.1973-5] Перейти обратно: ^а ^б Хаяси, Такеши (1973). «О деревьях вывода индексированных грамматик: расширение uvwxy - теоремы» . Публикации НИИ математических наук . 9 : 61–92. дои : 10.2977/prims/1195192738 .

[6] Хопкрофт и Ульман (1979), ^[1] Библиографические примечания, стр.394-395.

[7] Альфред Ахо (1969). «Вложенные стековые автоматы» . Журнал АКМ . 16 (3): 383–406. дои : 10.1145/321526.321529 . S2CID 685569 .

[8] Майкл Дж. Фишер (1968). «Грамматики с макроподобными произведениями». Учеб. 9-я Энн. IEEE симп. по теории коммутации и автоматов (SWAT) . стр. 131–142. дои : 10.1109/SWAT.1968.12 .

[9] Шейла А. Грейбах (1970). «Полные AFL и вложенная итерационная замена» . Информация и контроль . 16 (1): 7–35. дои : 10.1016/s0019-9958(70)80039-0 .

[10] ЦЭ Майбаум (1974). «Обобщенный подход к формальным языкам» . Журнал компьютерных и системных наук . 8 (3): 409–439. дои : 10.1016/s0022-0000(74)80031-0 .

[11] Роберт Х. Гилман (1996). «Сжимающая лемма для индексируемых языков». Теоретическая информатика . 163 (1–2): 277–281. arXiv : математика/9509205 . дои : 10.1016/0304-3975(96)00244-7 . S2CID 14479068 .

[12] Роберт Х. Гилман (сентябрь 1995 г.). «Сжимающая лемма для индексируемых языков». arXiv : математика/9509205 .

[staudacher1993-13] Перейти обратно: ^а ^б Штаудахер, Питер (1993), «Новые рубежи за пределами контекстной свободы: DI-грамматики (DIG) и DI-автоматы». (PDF) , Шестая конференция Европейского отделения Ассоциации компьютерной лингвистики (EACL '93) , стр. 358–367.

[14] Дэвид Дж. Вейр; Аравинд К. Джоши (1988). «Комбинаторные категориальные грамматики: порождающая сила и связь с линейными системами контекстно-свободного переписывания» (PDF) . Учеб. 26-е заседание доц. Вычислить. Линг . стр. 278–285.

[15] Согласно Штаудахеру (1993, стр.361 слева, раздел 2.2), ^[12] название «линейные индексированные грамматики» не использовалось в статье Газдара 1988 года, но появилось позже, например, в Weir and Joshi (1988). ^[13]

[gazdar1998-18] Газдар, Джеральд (1988). «Применимость индексированных грамматик к естественным языкам». В У. Рейле и К. Рорере (ред.). Анализ естественного языка и лингвистические теории . Исследования в области лингвистики и философии. Том. 35. Издательство Д. Рейделя. стр. 69–94. ISBN 978-1-55608-055-5 .

[19] Газдар (1988), Приложение, стр.89.

[21] Газдар 1988, Приложение, стр.89-91.

[vijayshankarAndWeir1995-22] Виджай-Шанкер, К.; Вейр, Дэвид Дж. 1994. (1994). «Эквивалентность четырех расширений контекстно-свободных грамматик» . Теория математических систем . 27 (6): 511–546. дои : 10.1007/bf01191624 . S2CID 12336597 . {{cite journal}}: CS1 maint: числовые имена: список авторов ( ссылка )

[23] стр.517-518

[BenthemMeulen2010-24] Йохан ФАК ван Бентем; Алиса тер Меулен (2010). Справочник по логике и языку (2-е изд.). Эльзевир. п. 404. ИСБН 978-0-444-53727-0 .

[2]

[примечание 1]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[14]

[заметка 2]

[заметка 3]

[15]

[16]

[примечание 4]

[17]

[18]

[19]

[20]

[12]

[1]

[13]