1. Oleg Sychev Avatar Oleg Sychev
  2. POAS Moodle plugins
  3. Moodle Plugins
  4. Issues

Пересечение съедающих и не съедающих переходов

Issue #339 closed
Former user created an issue

Originally reported on Google Code with ID 339

Проблема та, что обсуждалась на консультации, что пересекать надо начинать с разных
вершин. Пример (?=a)(b|^).

Reported by eklepilkina on 2015-03-30 16:10:41

Comments (30)

  1. Oleg Sychev repo owner 
    Валерий, обратите внимание на эту интересную структурную проблему тоже.

    Reported by oasychev on 2015-03-30 21:41:13

  2. Oleg Sychev repo owner 
    Лена, а вариант "пропускать до первого съедающего перехода" не годится? Ведь у нас сложный
ассерт посреди начальной (конечной) цепочки несъедающих переходов начать мержиться
не может?

Теоретически в случае ассерта внутри другого ассерта мог бы, но если есть вложенные
- то можно по идее сначала вложенный ассерт смержить с основным, а потом уже основной
ассерт - с самим регексом.

    Reported by oasychev on 2015-03-30 21:43:04

  3. Former user Account Deleted 
    Пропускать не получится при альтернативе со съедающими. Вот смотрите (?=ab)(a|^)
Автоматы для этого регекса t3 и t4. Если пропускать, то надо в одном случае начинать
пересечение с 0 в другом с 1. Я думаю, можно их преобразовывать как на t5 и t6, и тогда
можно будет пересекать с 0,0.

    Reported by eklepilkina on 2015-03-31 13:52:34

    <hr> * Attachment: t3.png<br>t3.png * Attachment: t4.png<br>t4.png * Attachment: t5.png<br>t5.png * Attachment: t6.png<br>t6.png

  4. Oleg Sychev repo owner 
    Как раз пропускать при альтернативе получится. Имеется ввиду что начинается от нулевого
узла, но в каждой ветке при поиске перехода с которого начинается мержинг несъедающие
переходы пропускаются...

    Reported by oasychev on 2015-03-31 17:30:38

  5. Former user Account Deleted 
    Не поняла. вот на том примере, я беру a из второго автомата, и пересекаю с a из альтернативы,
а крышку я пропускаю. И во фронте у меня уже первая вершина из второго и я должна брать
дальше для пересечения b. Но это только для перехода a. Для ветви с ^ мне нужен переход
0 -> 1 по a. Т.е. получается разница в 1 переход по пересечению.

    Reported by eklepilkina on 2015-03-31 17:37:43

  6. Oleg Sychev repo owner 
    Ну да, вы все правильно и говорите. Просто встретив "крышку" она по идее должна себя
повести похожим образом, как и при эпсилоне исходный алгоритм пересечения - пропустить
ее и мержить дальше - с той разницей, что крышка остается на месте, а не исчезает как
эпсилон...

    Reported by oasychev on 2015-03-31 17:44:11

  7. Former user Account Deleted 
    Ну тогда придется делать какую-то карту и хранить для каждого отдельного состояния из
первого автомата фронт волны из второго, разве нет?

    Reported by eklepilkina on 2015-03-31 17:58:45

  8. Oleg Sychev repo owner 
    Давайте для начала представим что в той же альтернативе вместо крышки - эпсилон. Как
будет работать тогда? Чтобы не было совсем непонятно, дадим ему тег - т.е. регекс типа
 (?=a)(b|())

Как в этом случае должно смержится, ведь проблема аналогичная?

P.S. Не думаю что нужна карта, все скорее всего решаемо развилками по ходу алгоритма...

    Reported by oasychev on 2015-03-31 18:06:36

  9. Oleg Sychev repo owner 
    Кстати, а если крышка уйдет в mergedbefore при мержинге с а - будут проблемы? Или если
будут - можно ее туда временно положить, а потом пройтись по автомату и извлечь, сдвинув
влево.

    Reported by oasychev on 2015-03-31 18:12:52

  10. Former user Account Deleted 
    В Вашем примере мержить не с чем, потому что переход соединяет конечную и начальную

    Reported by eklepilkina on 2015-03-31 18:15:20

  11. Former user Account Deleted 
    А почему мой вариант не подходит?

    Reported by eklepilkina on 2015-03-31 18:16:08

  12. Oleg Sychev repo owner 
    Ну так и в вашем с крышкой не с чем. И проблема одинакового рода.
Ваш вариант - это с волной? Это в принципе моя первая мысль, но там сложнее избежать
ситуации чтобы вторая ветка пришла после a - не перед ней, узел то схождения один.
По идее вариант с mergedbefore будет проще в реализации, нет?

    Reported by oasychev on 2015-03-31 18:19:24

  13. Former user Account Deleted 
    https://code.google.com/p/oasychev-moodle-plugins/issues/detail?id=339#c3 Вот этот.
Добавление eps вперед, чтобы пересекать несъедающие с несъедающими

    Reported by eklepilkina on 2015-03-31 18:20:59

  14. Former user Account Deleted 
    А ну соответственно и в конце также, если та же проблема.

    Reported by eklepilkina on 2015-03-31 18:22:25

  15. Former user Account Deleted 
    С фронтами сложно, не факт  что получится для верхней ветке там будет 1 вершина, для
нижней 0. Как отличать их непонятно.

    Reported by eklepilkina on 2015-03-31 18:24:08

  16. Oleg Sychev repo owner 
    А что дает добавление эпсилона? Напрямую ведь пересечения с эпсилоном не происходит...

    Reported by oasychev on 2015-03-31 18:31:22

  17. Oleg Sychev repo owner 
    Вот этот вариант не лучше? https://code.google.com/p/oasychev-moodle-plugins/issues/detail?id=339#c9
- т.е. мержить эту a с крышкой, ставя при этом крышку (как мержащуюся влево) в mergedbefore...

    Reported by oasychev on 2015-03-31 18:32:14

  18. Former user Account Deleted 
    Почему не дает? Я же могу пересечь ^ с eps. там правильный автомат получается в результате.
А если мержить некуда? как тут (?=a)(b|()). всего один переход.

    Reported by eklepilkina on 2015-03-31 18:35:07

  19. Former user Account Deleted 
    Может мне проще подойти к Вам на перемене? У Вас есть пары завтра-послезавтра?

    Reported by eklepilkina on 2015-03-31 18:40:18

  20. Oleg Sychev repo owner 
    Это хорошо когда эта длина фиксирована,в таком простейшем примере. А если она вариабельна
- из-за развилок или циклов, сколько тогда эпсов добавлять?

Что значит мержить некуда? Почему я не могу объявить, что результат пересечения крышки
с чарсетом это чарсет, в котором крышка в mergedbefore? И эпсилон с тегами в моем примере
аналогично...

    Reported by oasychev on 2015-03-31 18:40:29

  21. Oleg Sychev repo owner 
    Завтра куча всего, только времени мало. С утра двоечники (но может и будет выдаваться
время, особенно в районе 9-30..10-30), потом лаба с 11-50 - там буду занят, это КНПО
- проверка ТЗ и ТП - потом консультация с 5 и 3-м курсом, там где-то после них или
во время можно...

    Reported by oasychev on 2015-03-31 18:41:53

  22. Former user Account Deleted 
    "Почему я не могу объявить, что результат пересечения крышки с чарсетом это чарсет,
в котором крышка в mergedbefore?" Потому что сломается \b. Там есть ^ как один из путей
развилки, и она не должна пересекаться с чарсетом, там станут получаться ложные пути.
А идея пересечения должна быть общая.

    Reported by eklepilkina on 2015-03-31 18:48:11

  23. Former user Account Deleted 
    Ладно, давайте это оставим до следующей консультации.

    Reported by eklepilkina on 2015-03-31 18:49:35

  24. Oleg Sychev repo owner 
    Нет, правила пересечения сложного ассерта и \b - они вполне могут различаться же. В
\b там вообще мержинг не с начала, а с середины.

    Reported by oasychev on 2015-03-31 18:51:42

  25. Former user Account Deleted 
    Пример (?=ab)(c|^)b
Если говорить, что a & ^ дают ^a, то получим в результате автомат ^ab. А это неправильно,
тут он пустой. Разве нет?

    Reported by eklepilkina on 2015-03-31 19:25:18

  27. Former user Account Deleted 
    Кстати, я сейчас подумала, с пропусканием получиться скорее всего без всякой карты.

    Reported by eklepilkina on 2015-03-31 19:35:29

  28. Oleg Sychev repo owner 
    Конечно - https://code.google.com/p/oasychev-moodle-plugins/issues/detail?id=339#c8

    Reported by oasychev on 2015-03-31 19:36:08

  29. Former user Account Deleted 
    Да я поняла как. Я просто уже подзабыла за 2 года, как я делала.

    Reported by eklepilkina on 2015-03-31 19:39:34

  30. Oleg Sychev repo owner 
    Лена, если остались проблемы - возвращайте в InProgress

    Reported by oasychev on 2015-07-03 20:24:06 - Status changed: Done

  31. Log in to comment
Assignee
Type
bug
Priority
minor
Status
closed
Component
–
Votes
0
Watchers
0
Jira: the preferred issue tracker for Bitbucket. Join the team!