Сообщение Re[6]: Внезапная задачка с грамматиками от 19.11.2024 0:07
Изменено 19.11.2024 0:21 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
Там как раз выполняются эти же операции на каждом шаге — ищется разность мн-в. ))
Да, Копилот правильно описал нахождение разности мн-в, но неправильно описал алгоритм целиком, бгг...
Т.е. незачем разбивать этот алгоритм этапы, где одним из этапов будет построение промежуточного автомата, как предложил глупый ИИ, если все эти же вычисления можно выполнять "оперативно" над каждым состоянием в процессе проверки.