Сообщение Re[6]: Внезапная задачка с грамматиками от 19.11.2024 0:07
Изменено 19.11.2024 0:19 vdimas
Re[6]: Внезапная задачка с грамматиками
Здравствуйте, Sinclair, Вы писали:
S>Вы предлагаете строить объединение двух автоматов, копилот — пересечение (инверсия автомата — операция, вроде бы, тривиальная).
Иногда нетривиальная.
Да и незачем это, и вообще Копилот знатно облажался, бо "стандартная" операция сравнения минимизированных ДКА именно это и делает — находит такие строки, которые распознаются одним автоматом, но не распознаются другим:
https://neerc.ifmo.ru/wiki/index.php?title=%D0%AD%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D1%81%D0%BE%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B9_%D0%94%D0%9A%D0%90
Там как раз выполняются эти же операции на каждом шаге — пересечение мн-в переходов. ))
Т.е. незачем разбивать этот алгоритм на построение промежуточного автомата, как предложил глупый ИИ, если все эти же вычисления можно выполнять "оперативно" над каждым состоянием в процессе проверки.
S>Вы предлагаете строить объединение двух автоматов, копилот — пересечение (инверсия автомата — операция, вроде бы, тривиальная).
Иногда нетривиальная.
Да и незачем это, и вообще Копилот знатно облажался, бо "стандартная" операция сравнения минимизированных ДКА именно это и делает — находит такие строки, которые распознаются одним автоматом, но не распознаются другим:
https://neerc.ifmo.ru/wiki/index.php?title=%D0%AD%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D1%81%D0%BE%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B9_%D0%94%D0%9A%D0%90
Там как раз выполняются эти же операции на каждом шаге — пересечение мн-в переходов. ))
Т.е. незачем разбивать этот алгоритм на построение промежуточного автомата, как предложил глупый ИИ, если все эти же вычисления можно выполнять "оперативно" над каждым состоянием в процессе проверки.
Re[6]: Внезапная задачка с грамматиками
Здравствуйте, Sinclair, Вы писали:
S>Вы предлагаете строить объединение двух автоматов, копилот — пересечение (инверсия автомата — операция, вроде бы, тривиальная).
Иногда нетривиальная.
Да и незачем это, и вообще Копилот знатно облажался, бо "стандартная" операция сравнения минимизированных ДКА именно это и делает, что требуется по условию — находит такие строки, которые распознаются одним автоматом, но не распознаются другим:
https://neerc.ifmo.ru/wiki/index.php?title=%D0%AD%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D1%81%D0%BE%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B9_%D0%94%D0%9A%D0%90
Там как раз выполняются эти же операции на каждом шаге — ищется разность мн-в. ))
Копилот правильно описал нахождение разности мн-в, но неправильно описал алгоритм целиком, бгг...
Т.е. незачем разбивать этот алгоритм на построение промежуточного автомата, как предложил глупый ИИ, если все эти же вычисления можно выполнять "оперативно" над каждым состоянием в процессе проверки.
S>Вы предлагаете строить объединение двух автоматов, копилот — пересечение (инверсия автомата — операция, вроде бы, тривиальная).
Иногда нетривиальная.
Да и незачем это, и вообще Копилот знатно облажался, бо "стандартная" операция сравнения минимизированных ДКА именно это и делает, что требуется по условию — находит такие строки, которые распознаются одним автоматом, но не распознаются другим:
https://neerc.ifmo.ru/wiki/index.php?title=%D0%AD%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D1%81%D0%BE%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B9_%D0%94%D0%9A%D0%90
Там как раз выполняются эти же операции на каждом шаге — ищется разность мн-в. ))
Копилот правильно описал нахождение разности мн-в, но неправильно описал алгоритм целиком, бгг...
Т.е. незачем разбивать этот алгоритм на построение промежуточного автомата, как предложил глупый ИИ, если все эти же вычисления можно выполнять "оперативно" над каждым состоянием в процессе проверки.