Алгебраические и аналитические методы для доказательства неоднозначности грамматик

Макаров Владислав Маратович
Бесплатно
В избранное
Работа доступна по лицензии Creative Commons:«Attribution» 4.0

Эта работа состоит из двух больших более-менее независимых частей.

Первая часть посвящена GF(2)-грамматикам для ограниченных языков.
Она представляет из себя сильно упрощённую редакцию моей
бакалаврской работы с парой новых результатов. Упрощение достигнуто
за счёт более аккуратного использования алгебраической структуры
изучаемых объектов.

Вторая часть раньше нигде не публиковалась и посвящена
задача эквивалентности для однозначных грамматик. Получен
алгоритм для частного случая, когда симметрическая разность
языков разрежена. Также получен кубический по времени
алгоритм, сравнивающий языки только по строкам длины n
Наконец, предъявлен план, который в идеале может свести
задачу к известной гипотезе в теории PI-колец.

1 Introduction 3
2 Bounded languages described by GF(2)-grammars: a simpler retelling 4 2.1 BasicsofGF(2)-grammars………………………… 4
2.2 Subsetsofa∗b∗ ……………………………… 6
2.3 Themainresultforsubsetsofa∗b∗ ……………………. 7
2.4 UsingTheorem1…………………………….. 8
2.5 Subsetsofa∗b∗c∗ …………………………….. 11
2.6 Thelanguage{anbncn|n 0}anditsrelatives……………… 13
2.7 Areconversestatementstrue?………………………. 16
2.8 Conclusion………………………………… 17
3 Why was not the equivalence problem for unambiguous grammars solved back in 1973? 18
3.1 Equivalenceproblemforunambiguousgrammars . . . . . . . . . . . . . . . . . 18
3.2 Semenov’sapproach …………………………… 19
3.3 Matrixsubstitutionandpolynomialidentities . . . . . . . . . . . . . . . . . . . 21
3.4 Whatcanwedowithmatrixsubstitution?………………… 23
4 CYKSZ algorithm and its relatives 25
4.1 Cocke Younger Kasami Schwartz Zippel algorithm . . . . . . . . . . . . . . . . 25
4.2 Relationstocircuitcomplexity ……………………… 28
4.3 Matrix substitution and noncommutative determinant . . . . . . . . . . . . . . 30
4.4 Canwedothesamewithconjunctivegrammars? . . . . . . . . . . . . . . . . . 31

GF(2)-grammars, recently introduced by Bakinova et al. [4], and further studied by Makarov and Okhotin [21], are a variant of ordinary context-free grammars, in which the disjunction is replaced by exclusive OR, whereas the classical concatenation is replaced by a new operation called GF(2)-concatenation: K ⊙ L is the set of all strings with an odd number of partitions into a concatenation of a string in K and a string in L.
There are several reasons for studying GF(2)-grammars. Firstly, they are a class of gram- mars with better algebraic properties, compared to ordinary grammars and similar grammar families, because the underlying boolean semiring logic was replaced by a logic of a eld with two elements. As we will see later, that makes GF(2)-grammars lend themselves very well to algebraic manipulations.
Secondly, GF(2)-grammars provide a new way of looking at unambiguous grammars. For example, instead of proving that some language is inherently ambiguous, one can prove that no GF(2)-grammar describes it. While the latter condition is, strictly speaking, stronger, it may turn out to be easier to prove, because GF(2)-grammars have good algebraic properties and are also closed under symmetric di erence, meaning that more tools can be used in the proof.
Finally, GF(2)-grammars generalize the notion of parity nondeterminism to grammars. Re- call that the most common types of nondeterminism that are considered in complexity theory are classical nondeterminism, which corresponds to an existence of an accepting computation, unambiguous nondeterminism, which corresponds to an existence of unique accepting com- putation and parity nondeterminism, which corresponds to number of accepting computations being odd.
Tying to the theme of connections between unambiguous and GF(2)-grammars, classical and parity nondeterminism can be seen as two di erent generalisations of unambiguous non- determinism: if the number of accepting computations is in the set {0, 1}, then it is positive (classical case) if and only if it is odd (parity case); the same is not true for larger numbers, of course.
The main result of the rst part of this thesis is Theorem 6 that establishes a strong neces- sary conditions on subsets of a∗1a∗2 . . . a∗k that are described by GF(2)-grammars. Theorem 5, a special case of Theorem 6, implies that there are no GF(2)-grammars for the languages L1 :={anbmcl |n=morm=l}andL2 :={anbmcl |n̸=morm̸=l}.
As a consequence, both are inherently ambiguous. For L1, all previously known arguments establishing its inherent ambiguity were combinatorial, mainly based on Ogden’s lemma.
Proving the inherent ambiguity of L2 was a long-standing open question due to Autebert et al. [3, p. 375]. There is an interesting detail here: back in 1966, Ginsburg and Ullian fully characterized bounded languages described by unambiguous grammars in terms of semi-linear sets [16, Theorems 5.1 and 6.1]. However, most natural ways to apply this characterization su er from the same limitation: they mainly rely on words that are not in the language and much less on the words that are. Hence, dense languages like L2 leave them with almost nothing to work with. Moreover, L2 has an algebraic generating function, meaning that analytic methods cannot tackle it either. In fact, Flajolet [11], in his seminal work on analytic methods for proving grammar ambiguity, refers to inherent ambiguity of L2 as to a still open question (see page 286).
The close relationship between GF(2)- and unambiguous grammars brings us to the second topic of the thesis: the equivalence problem for unambiguous grammars. It can be stated in the
3
following way: Is there an algorithm that takes two unambiguous grammars and tells whether they generate the same language or not? . It is an important, but di cult open problem in formal language theory. So far, only partial progress has been made. Most famously, it was positively resolved in two special cases: when one of the grammars is regular [24] and when both grammars correspond to a deterministic pushdown automaton [25] (languages recog- nized by DPDA are an important, but small subclass of languages described by unambiguous grammars). Moreover, the proof of the latter result is very long, technical and involved.

Заказать новую

Лучшие эксперты сервиса ждут твоего задания

от 5 000 ₽

Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям

    Нажимая на кнопку, я соглашаюсь на обработку персональных данных и с правилами пользования Платформой

    Хочешь уникальную работу?

    Больше 3 000 экспертов уже готовы начать работу над твоим проектом!

    Евгения Р.
    5 (188 отзывов)
    Мой опыт в написании работ - 9 лет. Я специализируюсь на написании курсовых работ, ВКР и магистерских диссертаций, также пишу научные статьи, провожу исследования и со... Читать все
    Мой опыт в написании работ - 9 лет. Я специализируюсь на написании курсовых работ, ВКР и магистерских диссертаций, также пишу научные статьи, провожу исследования и создаю красивые презентации. Сопровождаю работы до сдачи, на связи 24/7 ?
    #Кандидатские #Магистерские
    359 Выполненных работ
    Екатерина Д.
    4.8 (37 отзывов)
    Более 5 лет помогаю в написании работ от простых учебных заданий и магистерских диссертаций до реальных бизнес-планов и проектов для открытия своего дела. Имею два об... Читать все
    Более 5 лет помогаю в написании работ от простых учебных заданий и магистерских диссертаций до реальных бизнес-планов и проектов для открытия своего дела. Имею два образования: экономист-менеджер и маркетолог. Буду рада помочь и Вам.
    #Кандидатские #Магистерские
    55 Выполненных работ
    Дмитрий М. БГАТУ 2001, электрификации, выпускник
    4.8 (17 отзывов)
    Помогаю с выполнением курсовых проектов и контрольных работ по электроснабжению, электроосвещению, электрическим машинам, электротехнике. Занимался наукой, писал стать... Читать все
    Помогаю с выполнением курсовых проектов и контрольных работ по электроснабжению, электроосвещению, электрическим машинам, электротехнике. Занимался наукой, писал статьи, патенты, кандидатскую диссертацию, преподавал. Занимаюсь этим с 2003.
    #Кандидатские #Магистерские
    19 Выполненных работ
    Катерина В. преподаватель, кандидат наук
    4.6 (30 отзывов)
    Преподаватель одного из лучших ВУЗов страны, научный работник, редактор научного журнала, общественный деятель. Пишу все виды работ - от эссе до докторской диссертации... Читать все
    Преподаватель одного из лучших ВУЗов страны, научный работник, редактор научного журнала, общественный деятель. Пишу все виды работ - от эссе до докторской диссертации. Опыт работы 7 лет. Всегда на связи и готова прийти на помощь. Вместе удовлетворим самого требовательного научного руководителя. Возможно полное сопровождение: от статуса студента до получения научной степени.
    #Кандидатские #Магистерские
    47 Выполненных работ
    Вики Р.
    5 (44 отзыва)
    Наличие красного диплома УрГЮУ по специальности юрист. Опыт работы в профессии - сфера банкротства. Уровень выполняемых работ - до магистерских диссертаций. Написан... Читать все
    Наличие красного диплома УрГЮУ по специальности юрист. Опыт работы в профессии - сфера банкротства. Уровень выполняемых работ - до магистерских диссертаций. Написание письменных работ для меня в удовольствие.Всегда качественно.
    #Кандидатские #Магистерские
    60 Выполненных работ
    Дмитрий Л. КНЭУ 2015, Экономики и управления, выпускник
    4.8 (2878 отзывов)
    Занимаю 1 место в рейтинге исполнителей по категориям работ "Научные статьи" и "Эссе". Пишу дипломные работы и магистерские диссертации.
    Занимаю 1 место в рейтинге исполнителей по категориям работ "Научные статьи" и "Эссе". Пишу дипломные работы и магистерские диссертации.
    #Кандидатские #Магистерские
    5125 Выполненных работ
    Анна К. ТГПУ им.ЛН.Толстого 2010, ФИСиГН, выпускник
    4.6 (30 отзывов)
    Я научный сотрудник федерального музея. Подрабатываю написанием студенческих работ уже 7 лет. 3 года назад начала писать диссертации. Работала на фирмы, а так же помог... Читать все
    Я научный сотрудник федерального музея. Подрабатываю написанием студенческих работ уже 7 лет. 3 года назад начала писать диссертации. Работала на фирмы, а так же помогала студентам, вышедшим на меня по рекомендации.
    #Кандидатские #Магистерские
    37 Выполненных работ
    Рима С.
    5 (18 отзывов)
    Берусь за решение юридических задач, за написание серьезных научных статей, магистерских диссертаций и дипломных работ. Окончила Кемеровский государственный универси... Читать все
    Берусь за решение юридических задач, за написание серьезных научных статей, магистерских диссертаций и дипломных работ. Окончила Кемеровский государственный университет, являюсь бакалавром, магистром юриспруденции (с отличием)
    #Кандидатские #Магистерские
    38 Выполненных работ
    Ольга Б. кандидат наук, доцент
    4.8 (373 отзыва)
    Работаю на сайте четвертый год. Действующий преподаватель вуза. Основные направления: микробиология, биология и медицина. Написано несколько кандидатских, магистерских... Читать все
    Работаю на сайте четвертый год. Действующий преподаватель вуза. Основные направления: микробиология, биология и медицина. Написано несколько кандидатских, магистерских диссертаций, дипломных и курсовых работ. Слежу за новинками в медицине.
    #Кандидатские #Магистерские
    566 Выполненных работ

    Другие учебные работы по предмету

    Алгоритмы для динамических диаграмм Вороного
    📅 2021год
    🏢 Санкт-Петербургский государственный университет
    О локальных свойствах решений задач гидродинамики
    📅 2021год
    🏢 Санкт-Петербургский государственный университет
    Структуры комодулей на кольцах Чжоу флаговых многообразий
    📅 2021год
    🏢 Санкт-Петербургский государственный университет
    Полнота биортогональных систем для нескольких интервалов
    📅 2021год
    🏢 Санкт-Петербургский государственный университет
    Задача размещения элементов цепи поставок
    📅 2021год
    🏢 Санкт-Петербургский государственный университет