"Записки научных семинаров ПОМИ"
Том 546, стр. 259-267
Ограниченные языки, задаваемые GF(2)-грамматиками (анонс)
В. М. Макаров
Санкт-Петербургский государственный университет
mm_led@mail.ru
- Аннотация:
GF(2)-грамматики -- это относительно недавно введённое семейство формальных грамматик.
У них много хороших алгебраических свойств, а результаты про них зачастую позволяют
лучше понять классическое семейство однозначных грамматик. В этой статье доказываются
сильные необходимые условия для задаваемости GF(2)-грамматикой подмножеств
$w_1^* w_2^* \ldots w_k^*$, где $w_1$, $w_2$, $\ldots$, $w_k$
-- любые фиксированные строки. Для этого применяются алгебраические техники,
связанные с формальными степенными рядами. Дальнейшее применение полученных
результатов позволяет доказать существенную неоднозначность языка
$\set{a^n b^m c^\ell}{n \neq m \text{ or } m \neq \ell}$, долго бывшую открытым вопросом,
и дать новое, полностью алгебраическое, доказательство существенной неоднозначности
языка $\set{a^n b^m c^\ell}{n = m \text{ or } m = \ell}$.
Библ. -- 10 назв.
- Ключевые слова:
формальные грамматики, конечные поля, ограниченные языки,
однозначные грамматики, существенная неоднозначность языков
[formal grammars, finite fields, bounded languages, unambiguous grammars, inherent ambiguity]
Полный текст(.pdf)