Аннотация:
В этом докладе я расскажу о выразительной мощности GF(2)-грамматик: специального семейства формальных грамматик, введённого около 8 лет назад Бакиновой и др. Простыми словами, я про одни семейства языков докажу, что они задаются GF(2)-грамматиками, а про некоторые другие докажу, что они ими не задаются. Семейство GF(2)-грамматик примечательно тем, что у него есть много полезных алгебраических свойств, которыми не обладает семейство обыкновенных бесконтекстных грамматик. Более того, GF(2)-грамматики обобщают однозначные грамматики, что позволяет использовать их хорошие алгебраические свойства для доказательства существенной неоднозначности языков (то есть отсутствия для языка задающей его однозначной грамматики).
В основном доклад будет посвящён задаваемости GF(2)-грамматиками ограниченных языков, то есть подмножеств $w_1^* w_2^* \ldots w_k^*$, где $w_1, w_2, \ldots, w_k$ — любые фиксированные строки. Я докажу сильные необходимые и сильные достаточные условия задаваемости таких языков GF(2)-грамматиками. С помощью полученных результатов я покажу существенную неоднозначность нескольких языков, в том числе языка $\{a^n b^m c^k \mid n \neq m \text{ или } m \neq k \}$, чья существенная неоднозначность долго была открытым вопросом.
Все необходимые определения, включая определение GF(2)-грамматик, будут даны в процессе доклада.
Обратная связь: