formallanguageconstrainedpathquerying / formal-lang-course Goto Github PK

Хочется один документ с формулировками задач. Без дедлайнов и прочей процессуальной шелухи. А дедлайны пусть только в табличке будут.

И тестировать сложно, и толку в ней минимум.

Только достижимость

На основе GLL

• В конспект.
• Задачу. Куда бы её? И так много получается.

См. heli0dus#5

Жить с голым pip'ом как-то не круто, а самое главное — больно

В частности, после удаления некоторых задач получилось странное: максимальный балл за все задачи 140, а на тройку надо хотя бы 40. По крайней мере, в табличке так сейчас получается.

С текущим генератором графов для RPQ и CFPQ легко нарваться на ответы типа [set(), set(), set(), set()] в большой части тестов. Это может привести к адекватным на первый взгляд решениям, которые на самом деле некорректны.
Эту проблему можно попробовать решить двумя путями:

1. Curated набор тестов. Буквально по одному-двум на задачку, с гарантировано не пустым ответом.
2. Попробовать использовать генератор более плотных графов. Можно в комбинации.

Некоторые названия функций и классов получились не очень. Все пункты скорее всего требуют обсуждения.

• FiniteAutomaton клэшится с оным в pyformlang, предлагаю MatrixFA (ещё есть мысль просить не конструкторы, а статические методы типа from_pyformlang, иначе там какая-то дичь в конструкторе вылезает)
• project -> flc (formal lang course)
• paths_ends -> ???
• reachability_with_constraints -> ???
• TestReachability -> TestRPQ & TestCFPQ

Список будет пополняться

Предложить использовать pytest-benchmark в экспериментах.

Уже сейчас дублируются штуки типа

LABEL = "label"
IS_FINAL = "is_final"
IS_START = "is_start"

Точно можно смотреть вот сюда как на хороший пример того, что требует рефакторинга.

Точно можно

• выделить всю работу с графами
• собрать общую коллекцию запросов: регулярок, грамматик и т.д.
• унифицировать цункции проверки эквивалентности результатов

Может, если внимательно подумать, ещё что-то можно будет выделить и собрать в одном месте.

Можно зафиксировать язык. Останется придумать, как делать тесты максимально просто.

Он мало зачем нуден, а его удаление позволит сделать дедлайны более разумными, а не дотягивать до 30 декабря.

Из #141. Пока что размер графа ограничен 40, потому что в нашей реализации задача 6 тормозит. Стоит выяснить как дела у других решений, и от этого плясать с размером графа

Было много комментариев по поводу делайнов, количества попыток сдачи, баллов и т.д. Надо это дело ещё раз попробовать аккуратно записать.

Ну кто ж сейчас зависимости ручками обновляет

Законтриьбютить в pyformlang

• Строим DFA (можно сразу минимальный)
• BFS-ом генерируем строки. Примерно, как по графу.

Сейчас типизация Get_start для RSM описывается так:

[e](b) => RSM<t>
____________________________
[Get_start (e)](b) => RSM<t>

Это опечатка (кажется, что снизу должно быть [Get_start (e)](b) => Set<t>) или поразумевается не просто возврат вершин, а что-то другое (например, также возврат информации о том, для какого нетерминала каждая вершина является стартовой, но тогда все равно не ясно, почему именно RSM<t>)?

Сейчас в функцию КС достижимости попадает шаг построения троек вида (вершина, вершина, нетерминал). При постановке экспериментов этот шаг из некоторых функций пропадает, а из некоторых --- нет. Получаются не очень честные замеры.

Как решение --- на уровне домашек чётко разделять шаг построения матриц и преобразование матриц в тройки.

Братишки, родненькие! 🥺 Поделитесь видеолекциями курса, пожалуйста! Хочу написать парсер SQL, не хватает формальных знаний.

Ваши записи (не читал, но пробежался) "Материалы по достижимости с ограничениями в терминах формальных языков" это прям бомба! Лучшее что я находил на просторах русско и англоязычного интернета. Но полноценных лекций, конечно, не хватает.

• Информация за 2024: https://dataedinitiative.github.io/index.html
• Наброски за предыдущие годы: https://github.com/YaccConstructor/articles/tree/master/InProgress/FormLangTheoryForDataAnalysis