Аннотация:
GF(2)-грамматики – это относительно недавно введённое семейство формальных грамматик. У них много хороших алгебраических свойств, а результаты про них зачастую позволяют лучше понять классическое семейство однозначных грамматик. В этой статье доказываются сильные необходимые условия для задаваемости GF(2)-грамматикой подмножеств $w_1^* w_2^* \ldots w_k^*$, где $w_1$, $w_2$, $\ldots$, $w_k$ – любые фиксированные строки. Для этого применяются алгебраические техники, связанные с формальными степенными рядами. Дальнейшее применение полученных результатов позволяет доказать существенную неоднозначность языка $\{a^n b^m c^\ell\mid n \neq m \text{ or } m \neq \ell\}$, долго бывшую открытым вопросом, и дать новое, полностью алгебраическое, доказательство существенной неоднозначности языка $\{a^n b^m c^\ell\mid n = m \text{ or } m = \ell\}$. Библ. – 10 назв.
Полный текст:
PDF файл (404 kB)