Автоматы и формальные языки: снятие ε-переходов, детерминизация, минимизация, Томпсон, устранение состояний — авторское изложение

ru · official · sha256:bf80101136e806a0bdcdf133180c5112537d92b9b1dfd6398e12b3ab39b52d53RU

§1. Автомат, ε-замыкание, различимость и разбиение Конечный автомат задаётся конечным множеством состояний, конечным входным алфавитом, начальным состоянием, множеством принимающих состояний и отношением перехода. У ДКА переход тотален и однозначен; у НКА он даёт множество состояний; у ε-НКА допускаются переходы по пустому слову. ε-замыкание множества состояний — наименьшее множество, содержащее его и замкнутое относительно ε-переходов. Оно вычисляется обходом по ε-рёбрам; наименьшесть и есть то, что делает его единственным. Слово принимается автоматом, когда среди состояний, достижимых по нему из начального, есть принимающее. Язык автомата — множество принимаемых им слов. Два состояния ДКА РАЗЛИЧИМЫ, когда существует слово, переводящее ровно одно из них в принимающее. Отношение неразличимости есть эквивалентность; её классы и суть состояния минимального автомата. Минимальный ДКА единственен с точностью до переименования состояний — теорема Майхилла — Нероуда, и её доказательство остаётся в источнике. Разбиение множества состояний на классы уточняется, когда какой-либо класс делится на части. Алгоритмы минимизации суть разные порядки уточнения разбиения; различие между ними — именно в порядке и в выборе делителя. Регулярное выражение над алфавитом строится из пустого множества, пустого слова и символов алфавита операциями альтернативы, конкатенации и звезды. Перечень форм закрыт; расширения программных regex-движков — обратные ссылки, ленивые повторители, границы слова — регулярными выражениями в этом смысле не являются. Обобщённый автомат — автомат, рёбра которого помечены не символами, а регулярными выражениями. Он есть промежуточное представление §6 и в определение §1 не входит.

Referencing norms: AnswersHere, f-0043af83f5a5bd7a51c1c426, f-05612c11d54514a8e3220586, f-07947c97eeaf4a0cc995a749, f-11ef1081c4c7892a714fb568, f-12185710dfba364d23bcd948, f-129aa3f41406d5ec3da50ad7, f-16b085cf3e5f2d37906595ff, f-20219685042a16deed01354f, f-2a346ec78a316ef602c17edf, f-2f014c1084422a59e849f9f9, f-331d103ec360ee5d7ea6edad, f-3a1ec6fbb3f23589bb6b7662, f-3fbb17695cde315a02c6cb39, f-40172744979d366551d30549, f-4f368190cec26894ec98b42b, f-57aa14b7df9bb45aa6e575d5, f-5d7a1307c97c6cc4cd3bf50e, f-5f4546456c32d1ca631ebdd6, f-5f5c6d23663d8091d35b5518, f-669a15a1ba1d1ef6b34660ee, f-69f86138460b704821842bd8, f-6c9542d3d87241ee574548ce, f-78220d9abfa5d5d6869abd2d, f-7c0c29bf49c56a926d631c88, f-848f70e456403cb70211e89b, f-8d4fac6a0217c68636f540c6, f-9129237283f1e9bea694f53d, f-9476008c99c881ee5aeef7bf, f-97d6c893e83979a791b102a1, f-9edec293a0fab16cab205d11, f-a0a7fdc9d58c6a5fc5fd1b08, f-a6df24034e3a30d557489b07, f-af94908eaf34a5dd8655c936, f-b23f0e422ecc1c3e3802f519, f-ba803ca1407cb2084aceda59, f-bcfba526b85f265ec01ef5b8, f-bd998c7e51ebc628a3b0aea5, f-c0daa436250440e91c238512, f-d3ff1cab8a3ac685ce447f29, f-e52c557942b060aea732e336, f-e7e3c0afb9dbda80f307333d, f-e95789d47b8f815741016859, f-f08066d9b9c15c7d4681b6ee, f-f3a5fe571f830776a730bed0, f-fd1bf1c2838263bb4d673cbe, f-feafbf8cfe89c0496c3cb72d

ru · official · sha256:9e6468de782608e3b4ea42d0462ff83badc4cca9418a3e24193339934e94f25cRU

§2. Устранение ε-переходов Задача: по ε-НКА построить НКА без ε-переходов, принимающий тот же язык. Вариант — через ε-замыкания состояний. Для каждого состояния вычисляется его ε-замыкание. Новый переход из состояния по символу ведёт во все состояния, достижимые так: сначала по ε-замыканию, затем одним переходом по символу, затем снова по ε-замыканию. Состояние объявляется принимающим, если его ε-замыкание содержит принимающее состояние исходного автомата. Тройная композиция «замыкание, символ, замыкание» существенна. Пропуск последнего замыкания — самая частая ошибка изложений: без него теряются слова, у которых после последнего символа идут только ε-переходы к принимающему состоянию. Начальное состояние остаётся прежним, но его принимаемость пересчитывается по общему правилу: если ε-замыкание начального содержит принимающее, пустое слово принадлежит языку, и начальное состояние обязано стать принимающим. Инвариант: язык нового автомата совпадает с языком исходного на всех словах длины, не превосходящей уже обработанной. Оценка: вычисление всех ε-замыканий стоит порядка произведения числа состояний на число ε-рёбер; построение переходов — порядка произведения квадрата числа состояний на размер алфавита. Число состояний не растёт — этим вариант и ценен.

Referencing norms: f-0097506ee71a735169f05f24, f-0408d117163e00469dea4030, f-045ca29086f4435a60a71e00, f-06e79a6f41bf687fecd741e7, f-095153ff57525f9a891a5bb4, f-09f17d6fe17d131554915e70, f-1049511794637bb64d3955b9, f-10dcb57bc3000b2df1c67d4a, f-12c66c4d102dd17ab8088500, f-137ea8eb8713993160526a77, f-18c47a88516796289bc49180, f-1964321bfcf32c830ac10eda, f-1aa4b86c0b0a99115e241145, f-1b9f04c5d78b183135142719, f-1c8ac5cb4ba6ad2c6cef0adf, f-2772f104bc9517e7eb6bc74e, f-29459a09b7f6e53e7d2caa5b, f-2a47e3c51e161fd36f0ab532, f-2b6c9862c414c61f4881f4e2, f-2c140dc251426e3af8d59ee2, f-3178e03ca3c12b3fda3e6ae9, f-32596ee6722291d2dc9f0577, f-3478eab6467bf628b44bbd01, f-35e2144b094b7bc9c4ec0247, f-3628c2ed3e9407899a1c1e82, f-3ad12e2eb907467b4dd47958, f-4611a7c40e539daa83d3b4be, f-483b3311831e67afeccb4552, f-4b654210761b8881821c91b8, f-4d08ca9556e82057ff5f4234, f-4f6156565288c233aa2baaf4, f-4f97a22257a249c8dc5c45b3, f-4ffb5717df08e6fe50684166, f-50cb2db2e00648cdfc8ae575, f-5e206a32c3f341ffd2734d74, f-659c73e5f1e9526b24fb633b, f-6875c226f37c25779aff80e8, f-6a0742c6b0b41a6a981dcde4, f-6c85d316c8342a03324a527e, f-70a7f271eef1520025b67032, f-725492bebd80babc6fd4333f, f-7e28975dbd3c7d87ce29f3da, f-8412096431556c0ab2bd2dbf, f-91eecbd457bb6f8829a14cf7, f-982721d2a1d5a484d6e53788, f-985977fa5d0ed539a30e554c, f-9bda0bd3e686f894c62a8d46, f-9cdbffba4297f432d27daac5, f-9e5939bb5ee6b9ccf3820762, f-9e6fc5f35eb4c032f10fa7ae, f-9f3823b9649430735286f290, f-a1a183502343f11767774747, f-a705277653b9c39decd42a35, f-a742158be6f9ea516c0ed32b, f-a944a4752c2dbf37966335c4, f-ad368719e116f3428238da29, f-b0b7d05b9239e588698bcaa5, f-b5c138805ccfcc7ea2cb4de5, f-b9cc3654e9c86c8503c407b7, f-be26765deec25407bb64cb09, f-be3f17a932869501cd8231c9, f-c4e8073b61e2147400f28336, f-c5d6caa72237922a9d0a9e2f, f-c66d595c5c32f2c204be6ac6, f-ca80e79771d38e8663d5ac0e, f-cdc280a9c1074b1c06cfa61f, f-cfa7c567aa1067d9180d4dd0, f-d2b156519196a80a171ef434, f-d9d2db4e61e7f4c0e97b8cfe, f-dcc7fc3d60a7c95e1b58595f, f-dea8eb00a4f1fa763d24684d, f-e5bf6ba97a72419baf762721, f-e787f40486bc77420b54bd3f, f-ea47f158e0d7b52fa712217e, f-ed60f58986dfd73ed274497b, f-f5ca47ddb82b21bd0dd83d0d, f-fb41a9adb4801868f73625bd, f-fc32f099476fe81d9761bac6, f-fd586bb3e82d11f641c677d7, f-ffa1c1c05d3936978c215f74

ru · official · sha256:7012a0f5ded4e610632068801fb003d4aa531c7d1c8b2fc4fc1f03d6204d19caRU

§3. Детерминизация методом подмножеств Задача: по НКА построить ДКА, принимающий тот же язык. Вариант — построение по достижимым подмножествам с ленивым порождением. Состояниями строимого ДКА служат ПОДМНОЖЕСТВА состояний исходного автомата. Начальное состояние — ε-замыкание начального состояния исходного. Переход из подмножества по символу ведёт в ε-замыкание объединения переходов всех его элементов по этому символу. Подмножество принимающее, когда содержит принимающее состояние исходного. Строятся только ДОСТИЖИМЫЕ подмножества: обход начинается с начального и порождает новые по мере надобности. Порождение всех подмножеств сразу дало бы два в степени числа состояний состояний всегда, тогда как достижимых обычно немного. Ленивое порождение — не оптимизация, а часть варианта. Основание корректности — теорема о детерминизации: язык, принимаемый НКА, принимается и некоторым ДКА. Теорема закреплена пакетом `hws.regular_languages`; настоящее описание применяет её формулировку и предъявляет само построение, которого теорема не даёт. Инвариант: множество состояний исходного автомата, достижимых по прочитанному слову, равно подмножеству-состоянию строимого ДКА, в котором он оказался. Оценка: в худшем случае число состояний ДКА равно двум в степени числа состояний НКА, и эта граница достижима — утверждение источника. Отсюда и предел применимости: построение может дать автомат экспоненциального размера, и это свойство задачи, а не метода.

Referencing norms: f-05ea3b0ba9cf2e4f63e73921, f-0a91499fbff560802bf6682c, f-0ed69218d468c0845a0d179d, f-10d59e7daf8e9ebb5ab4e8ab, f-18731c88860a111d6f528571, f-1ed3ade573d8ba2bb3b14ea6, f-22e8ee64cb9c3f16869ebe52, f-23712b74aa5ec5cd3d08d287, f-23a1016d65597a4acfcd0ee9, f-2480fe59ffc61ecbe40961fd, f-263a121d5b22546157b64f00, f-27895b6b5891c85888a4bf19, f-281fd86d513d956cfa2f7a3f, f-2bb6788409b11b018730fda9, f-2cf3e68287623b084f22062f, f-2dccfdc71f7c44b9164a0e12, f-2df8e80613d7577201ca310e, f-320328b785812c3b8cbc4ae5, f-3aa1a4c7a4ca34a66832a354, f-3e72258a8c8a76578be15df2, f-3eedc9d6053a7438463e2b59, f-3f70f0da56af1a5b3c8b6651, f-40595be7dca3216bb78229aa, f-4387c6d51e6fdd5c1d0ab115, f-46c547e07903cd2d83e2532f, f-475397842f436c4d0cd63fee, f-4a0e8c5eccd14840275a7ac0, f-4b336cba21c64cd0d393dc84, f-4ecfc04d54e89e8f10005684, f-4f0a051f254d7a08a6219180, f-4fd39439a46e0356340d49d8, f-553454bd9698b4f0a147af82, f-561bf19cbf3d328c4b495139, f-564b30b5b9d59b9b5ac18e6e, f-572a6da0cf1615142fe91503, f-58e4c2ddf4d1674095ff45aa, f-5b5ce3e905c2cdeef33814b2, f-5bb897f52d8fcb9f5246978f, f-61e005ef1677e5304adf32ca, f-645ea2dc7859b97e41cc23b4, f-647ef968dab7d888b636063e, f-65ef7b4d890d9409453f9db0, f-66b48b8f2b6745abeb0c927f, f-6f101fd5505ef61facced896, f-70acd1ef8bf912468f4dc793, f-7535b5511284b67405f7de58, f-785a0cd7bcf0df0322c524b8, f-789d5664d6cceb064214b25f, f-78dc72cb7e5dd70b012f9c56, f-80de52a1ebb35697cd782156, f-85b7e850641338cc43a4e389, f-8e443358e11234c27494c34f, f-9135cfc29ed7681fd6d38052, f-925a18da9402391a82eae172, f-9f05f1d9a62bf726e4b4de0b, f-9ff2b14d21cc9ca9d2f8b41e, f-a15690291e928dabb4213716, f-a2922707c391d0c2c70ef029, f-a3e9e93ac7672f349113a8f7, f-aab00e7e57d07cdf756f2888, f-b33cd858c2fe7cec12f4265b, f-b3859fa717d32a69257564f9, f-b5b22f061470210476e81a63, f-bb0112a845dce94a36153d1b, f-be089b13bcc7f567df2fe699, f-be2a931a322750078281c543, f-c0f426f2c68e2be700a04281, f-c0f67d26e2e2c232de504c07, f-c5440141ffb048a80850310c, f-c662244c7efa78d1b38be71a, f-c72c935d84e80e69dfa81e7c, f-cc3e63ca76b9618d05835160, f-cf9d3e78ef542bef2861896f, f-d2c3de814a6cbc43ca71fd16, f-d4fa927e8d0e084487d7ceb2, f-d53444ce0519d24a681eae02, f-d7c9a6562001b4bcccabc378, f-d98a14774906e39be483c56c, f-d9986f60b74909aefbe5e40c, f-d9fa5eec51444469f3badd11, f-dcf833696084bee5f304e789, f-ddb3cd8342e41d2d0bc8b4e6, f-e2a664bb395d56f4cfbc5aa7, f-e5b6c79022a8f4ed6aefe83d, f-ebe15c944710d4cc47d028bd, f-eedf43ff2c17b7cc5726422a, f-eef7a9addf61af3d29f32a09, f-ef84662d2b351bfa3cbf5b7e, f-f4704a9b52c86e37fdefdc7d, f-f992e3bbec0350cee0811d64

ru · official · sha256:6c4c8b61ecd1132cdb0dbb6100ae6cc934e29131b3822c326cef470154be084bRU

§4. Минимизация ДКА алгоритмом Хопкрофта Задача: по ДКА построить эквивалентный ему ДКА с наименьшим числом состояний. Вариант — уточнение разбиения с очередью делителей и правилом МЕНЬШЕЙ ПОЛОВИНЫ. Начальное разбиение состоит из двух классов: принимающие и остальные. Поддерживается очередь пар «класс-делитель, символ». Пока очередь непуста, из неё берётся пара, и каждый класс разбиения делится на две части: те его состояния, что переходят по символу в делитель, и остальные. При делении класса на две части в очередь добавляется МЕНЬШАЯ из них. Правило меньшей половины и есть причина оценки n·log n. Добавление большей части не нарушило бы правильности, но дало бы квадратичную оценку — то есть алгоритм Мура. Различие вариантов состоит в этом одном правиле, и называть его обязательно. Инвариант: текущее разбиение грубее разбиения на классы неразличимости, то есть неразличимые состояния всегда лежат в одном классе. Мера убывания — суммарный размер элементов очереди с учётом того, что каждое состояние попадает в очередь не более логарифма от числа состояний раз; амортизационный довод принадлежит источнику. Предусловия существенны и обычно опускаются: автомат обязан быть ДЕТЕРМИНИРОВАННЫМ и ПОЛНЫМ, а недостижимые состояния — удалены заранее. Минимизация недетерминированного автомата вообще не является задачей с единственным ответом. Оценка: порядка произведения числа состояний, логарифма числа состояний и размера алфавита. Алгоритм Мура даёт квадратичную оценку тем же результатом.

Referencing norms: f-0070a2bff00cd3edb6026d90, f-0129a20c8d20c9c36fb3a67f, f-0413fcf1d856ba3b26ebb589, f-076e636ee5c81f136297282c, f-081be278fc92e2cd82aae268, f-091b9aca3b7488c5e4508272, f-0b560c15a3b5d6bf0af15f7a, f-0c3fd7c4febdb9248dccb138, f-0df80ef8eaa6b10b8ae3d0ad, f-0eafa86f824cae41ba323721, f-0f8c00cb5fb958140b2f2318, f-12e79c26e7eda3bd1cf3b48e, f-14b1d0e12bdd97fb515ab315, f-1875219805f27adcaf29aefb, f-191307f13a7f0a0df4aaac1f, f-1b63b1b3fa65eeb4411bf314, f-1e7825891a87c4a4f0a6ada6, f-1ee41b630405281418eccd3a, f-20947746545b91b94837f9fc, f-220e506738c21c02422fd0dd, f-2b424d2876ff42aea504dd09, f-2dc37184aaa2c3792fed684b, f-2fb5bf40e7e10e0324214ff7, f-34c80f1ad30af303a0aab7b7, f-390bf53152d869c34b5b2e36, f-3923c251e2cdbd5cb449c230, f-3cd163658d8d36f927cbe467, f-42205a43d75ed2133ebabc42, f-468117cae14e8161867d0be6, f-4929cae567c19015c8b7f66a, f-4b1648734add1ce7126b311c, f-51e2934708985dcc0501726e, f-5301c0b6477bbb3cd2cd4a36, f-5309f66a630038b74901ef42, f-56401b5436a7073fac4f49ee, f-56b9231f2639118a0a8403ac, f-5b79a9f816e1277681d7f5a3, f-5c01114e086eb107c5f280c5, f-5d0cb121dcabd03c09f44c9d, f-5d67ed131a7bec230cf2dc77, f-65116c7d86bba6be0db6d259, f-67900ee8b8f07371af86fe4a, f-68a67a93a32ca03be4b46262, f-69435babc99f77c281d10c57, f-6ac2509eea504e3c01319b68, f-6ad3ef014d219874a4454ae6, f-6d55dbb16e621530483841e8, f-7043f584e2fc6948a85b170e, f-77026a8efff3d67c4c79074f, f-77abed75bec669e4f89cfce6, f-780c61c5f51d81aa44230dd4, f-782f0d551d688952142cf91a, f-7e4445e59574de2e5d57bb06, f-80d80316085dd1798c6ff781, f-825274264876718334bdfdb5, f-83ea4e35b2f72f30e8659427, f-862606037892f89df9132dd3, f-86d8dac201708c7e576d0475, f-8ad6490d58872f812360bd23, f-8b91d8059df9ef734ec8638d, f-8bed8502239091f7df891f65, f-90f52d8bbd2584bb080ec04a, f-91819e801c2a58aab4d210b2, f-92cd4ab5d53b05c556f3fdc7, f-98e9573689065e15d297a559, f-a0201b97cf338158cc5ff0f7, f-a12c191976e842126425d500, f-b3870001fc51c130294f771e, f-b4cd48d6da915d51368eab86, f-b8aaf9c1f940ae1361a09594, f-bdb319e8790fde2c69a8ad20, f-bdfec26ebaec62d382183cf9, f-c3235b68cd7f677de66635e0, f-c4ceef298d73e69198d40ddb, f-c62f96e6135a6069c1a728cb, f-c758f1bb3bec18ce2f9dfaab, f-c810518c2deed0d4c72cf5d7, f-cc45d4a74629a76a507a9d41, f-d18f40ef093b4c3552376467, f-d8ce6ff3640a8848f132f008, f-e22f9a63538350c6ebdaf124, f-e56ad3dbc68e08eeaa3c0452, f-e6ad1f6f7fbce6b494bd4cca, f-eb57b350f9ea7d0c267e42eb, f-ee9745f8e7c42b2ea0e08b6d, f-ef53099121228a6d511a1e4a, f-f1d79737944201ac351e1703, f-f26576b93af0ac3430efebc8, f-f2bd3f7d73533b425e901a0e, f-f432568bc0fd14ab2fa36275, f-f61e9785545a2d035a9324b7, f-f9b639ac4c3ee724c50fb0c0, f-fb4ba2a97adb864db48fc4cf, f-fcfc3cbaf1274d08e5fc40e7, f-fe87b1e132e89df74d334fe8

ru · official · sha256:cc5c412c4bff84475efcdf485fe22064e70a427530ad63b6fd40225acb8ac9c6RU

§5. Построение автомата по регулярному выражению методом Томпсона Задача: по регулярному выражению построить ε-НКА, принимающий порождаемый им язык. Вариант — рекурсивный по структуре выражения, с ровно одним начальным и одним принимающим состоянием у каждого фрагмента. Каждой форме выражения отвечает свой фрагмент. Пустое множество — два состояния без переходов. Пустое слово — два состояния и ε-переход между ними. Символ — два состояния и переход по символу. Альтернатива — новое начальное состояние с ε-переходами в начала обоих фрагментов и новое принимающее с ε-переходами из их концов. Конкатенация — ε-переход из конца первого фрагмента в начало второго. Звезда — новые начальное и принимающее состояния с ε-переходами, включая обход и возврат. Свойство «ровно одно начальное и ровно одно принимающее состояние у каждого фрагмента» есть ИНВАРИАНТ построения; на нём стоит вся композиция, и без него правила альтернативы и звезды перестают быть локальными. Фрагменты НЕ разделяются между вхождениями: каждому узлу выражения отводятся свои состояния. Разделение склеило бы разные вхождения одного подвыражения и изменило бы язык. Число состояний не превосходит удвоенного числа узлов выражения, число ε-переходов линейно. Это и есть главное свойство метода: размер автомата линеен по размеру выражения. Основание корректности — теорема Клини в части «язык регулярного выражения распознаётся автоматом». Теорема закреплена пакетом `hws.regular_languages`; настоящее описание предъявляет построение, которого сама теорема не даёт.

Referencing norms: f-07685d662235d510bca7eca7, f-0bc5e26de99e373789d5961d, f-0f1f64df4b070dc8f90ac444, f-1056bdb4a535ad00de170cca, f-11b4a545bc3a5debfac68ee1, f-13b0195b5c77b2cda2c55388, f-1580895e5c4848a57e1caadb, f-1723028e294cdf7538445c2e, f-1b9b3708252eba121648fe61, f-1e86ddc32fa0610ef1b293d0, f-22be186a2bdb23836511750b, f-2847213983cc432499478831, f-2a3656a14afb93525221d9dc, f-2ce841fe52cf89ede4bd456f, f-2cf2a89d15506768ade18d6e, f-2dc4d3f2cdc9408e85d95da4, f-37c571bb356b74e4acb52f70, f-382ffda850ef873b065f15ce, f-39fc151c13095935f6adb549, f-3ae084dfdb2dd6958121bd85, f-3c23ff6f27ee0fae1305268b, f-3dea9b94ac46f8a632afc8e2, f-453a3a13d7ad5d5aa4ac8971, f-48cb2e30d80edaca96695e3b, f-4a4abc77e048139cbeffa164, f-4a8dfa7897e6613436e514d6, f-4e7176503f9da79760fb78ba, f-5316ab0f5a50d5d588dc54af, f-539cba01b186c38d645f207d, f-558246aef6ad8f694b7fc4f9, f-56d7d78c35ed747bb581815a, f-57a34308cc1bc7882f588756, f-57f51853926921b6273062eb, f-5b0df6b1991050eb798d8cd6, f-5d41224a9ce930c3b0080e09, f-5dddd5eeefde19619b2347e8, f-5e1d6d14876184d829094bb9, f-6064990d998724367ef7d31c, f-69d4ec726a09edcd04a0952b, f-6d069b0403b7d42adbde02bc, f-6d671680bbcafa8592add6d2, f-6de04ffc0210c0d5171563a9, f-70fa89f14c874054918776d6, f-730dc7f4379e2e5f003eb2f6, f-740ead56fe3241f817b7eaae, f-779d8b7e0beef3a5b368caf8, f-7c6626f9db425f4073b12e1a, f-88604e0cd79dc638d5dfe616, f-88e259eaed4b037f33e602cd, f-8c2ab11a99d31c6c4b92004b, f-8c74948b90ea1a89427d29c9, f-8dc9b32c824de2394352085d, f-8ddbd50124f4c4589a019a78, f-8eeb5be712f45625dc17e7a0, f-922a318ffde41dd78308cc95, f-956f5c00da4ea48651fa6ec7, f-95dbc322ee8ef58581fe91da, f-97d5ffe64092edb924bad9ee, f-a31f301ba6ce7fec6d80030f, f-a5446e8497ddd4a6f37ef2f6, f-a5f801b1445c030deef3b6b2, f-a739ecb7275ffbdcbdc8157c, f-a7bff5a72ff7fbbe68abf8dd, f-a7decb52f6b7e2a089333838, f-a8d3155942adf7ff90bad2bc, f-ad3f288c323c23b55130472e, f-b12eb64fb3d57bed6809b3b6, f-b3a047faf846cb246d190226, f-b5f799f9662582688f8d4692, f-c125a3965891c67925491abf, f-c525164c2649303e1ed425fa, f-c673d49139833ae8b277c939, f-cbc591647a07a7d5f4967f5b, f-d33603f405c4b33891451b1e, f-d4a167b5ec12567b1be4cd91, f-d7a3c74e86dcce3a7e264eb6, f-d7c10ed876e63d35730e2a1e, f-e0a60e99111ba0680011753f, f-e19c5826473306d15acf2390, f-ed1c9edf1c8ecee26f429696, f-f229ab1fb765daa175466177, f-f5be269785ad03ba5357351f, f-f7c366d8216049044b8e03ba

ru · official · sha256:b121896c6376947374ce89108d7e0e706e9f4fb7fea55982f9923535905b0f45RU

§6. Получение регулярного выражения устранением состояний Задача: по конечному автомату построить регулярное выражение, порождающее его язык. Вариант — обобщённый автомат и последовательное устранение состояний. Автомат превращается в обобщённый: добавляются новое начальное состояние с ε-переходом в прежнее начальное и новое принимающее с ε-переходами из всех прежних принимающих; рёбра помечаются регулярными выражениями. Затем состояния, кроме двух новых, устраняются по одному. При устранении состояния q для каждой пары «входящее ребро из p, исходящее ребро в r» метка ребра из p в r заменяется альтернативой прежней метки и конкатенации «метка p→q, звезда метки петли q, метка q→r». Петля состояния q входит именно ЗВЕЗДОЙ: она может быть пройдена сколько угодно раз, включая ноль. Отсутствующее ребро понимается как ребро с меткой «пустое множество», а не как отсутствие пары. Без этого соглашения правило устранения приходится расписывать разбором случаев, и в разборе теряется случай отсутствующей петли. Порядок устранения состояний на ЯЗЫК не влияет и сильно влияет на РАЗМЕР выражения. Порядок есть параметр варианта; настоящее изложение фиксирует произвольный порядок и говорит, что выбор порядка ради краткости выражения — отдельная задача. Инвариант: язык обобщённого автомата не меняется при устранении состояния. Основание — вторая половина теоремы Клини: язык автомата порождается регулярным выражением. Теорема закреплена пакетом `hws.regular_languages`. Оценка: устранение одного состояния стоит порядка квадрата числа состояний операций над выражениями, всего — порядка куба. Размер получаемого выражения в худшем случае экспоненциален по числу состояний, и это утверждение источника обязано называться вместе с методом.

Referencing norms: f-04c970d3df76718e76c01fcc, f-092e18f871ed3f4b714cda6d, f-09c0e2a3870e1b17c3e9c7aa, f-0d6879a70b7d688f99ca596a, f-0e44fa6522df465359d02fa9, f-0eb2155f95a7225a0f95d9a1, f-10fd65089633cb7122004ca2, f-12aaa27f04516747ff669af5, f-13fdb606651da79dffc6c644, f-1b3cc658769596c4014e1a56, f-2ab692cdbcd53a1b66739c2c, f-348db70a1e5517877ea5790c, f-34d33c415df569fb95dc5c33, f-37d8ea9b97cb03f811fcdb83, f-386ce6b31f54e8f9204f1e4e, f-393aadfee6d4ad776279047d, f-3adf5c9298664022a7d7fd76, f-3f90bab05007e8a7a06d5dfe, f-43d7e81f2af68c664637aa95, f-57de985f7218d54fb3061223, f-59e03fbe4cdaf5a411ef032c, f-5b07dfc3e9c24894074225cf, f-5f79777950af4a22d6f801b8, f-6164ea01f30e32c2b0388cf4, f-622cd977137e48614401fed9, f-62623afaaa4021cc1a67b0a4, f-639c552852a9abf3e797ee4a, f-6579914b6217f420fda2b665, f-6b88955d31e32e7f091703b1, f-6fc202037ef8b96abeaf0374, f-71037795bd6ae97e81238f59, f-75c805ce5b639e525e3b0308, f-7b72a2f6c50e8f3ddde9cefa, f-7d0f78bf60ba86998df1c09d, f-8724c754ba0463ea30f4aa56, f-88e441f8867f7b0488d897c8, f-897264f9333a074063187938, f-8b7d8bf98144aacc59089bb7, f-8d26ed15e6a8494dca31f3c0, f-93636bea9c4c2f3332ecc804, f-9d245411f7a123606df1cc35, f-9e4db3dc2ac6029bfa4e82f1, f-a116ba70fd4408749bd0e0ed, f-a2d33a2eb186f76f24933d3e, f-a3d1aa31442ce4821e7f358b, f-a5b00ab2989d55c02c325887, f-b0fbf4cce4261eae60c5ba6c, f-b3eb2ff79b786434b526035c, f-b57b04a3c9d06626be4522f1, f-b59da4de7c7b8b83c6cea8dc, f-bcffa94f7a957d82a71b6438, f-bd2a2f931531fd890359f97a, f-c2794d9a35aef0205a1906b5, f-c88b38ccf6b12badbe6d95c2, f-c8a07bcaf197571aa82938a1, f-cced2940745c197cddf56444, f-cd0c2de92035375ebf2de27f, f-d1bb272a3d9c2217ea89af9c, f-d1d0b55b4eef0cc5c87bcb25, f-d7da13506ff7d34b5e74bcc7, f-db28367e17c3b40d396e0ddc, f-de24ea2f49bdf9248b9810e1, f-df118c04f2f20d915cfae72a, f-e11f864620ed842aa065cd5d, f-e1483d4b5bd4e86d47970ea5, f-e7239ec271f3da21a895515a, f-ecab61dbbe362469f4f77971, f-ef5c13ad4d995a447e45e76e, f-f25a6f58f19f6baf6ad62ee1, f-f4b0dc8906e78a8866ca9908, f-f719c0dbe30cccc2bf8a2a13, f-f87db6b4883cbc16acd291d7, f-f8e516062703519227fcecc5, f-fdcfc8ae20aac755a1dc767f, f-fe914ffcd3428964ae2092f8, f-ff02f683c98e87a82ebaa4ea

ru · official · sha256:9336b5b32a7e02a02e3ce8ab5bb4998cdf0908cf774decffce5b9647db507722RU

АВТОМАТЫ И ФОРМАЛЬНЫЕ ЯЗЫКИ: СНЯТИЕ ε-ПЕРЕХОДОВ, ДЕТЕРМИНИЗАЦИЯ, МИНИМИЗАЦИЯ, ТОМПСОН И УСТРАНЕНИЕ СОСТОЯНИЙ Настоящий документ является АВТОРСКИМ ИЗЛОЖЕНИЕМ, составленным для целей формализации. Он описывает устройство пяти алгоритмов над конечными автоматами и регулярными выражениями: устранения ε-переходов, детерминизации методом подмножеств, минимизации ДКА алгоритмом Хопкрофта, построения автомата по регулярному выражению методом Томпсона и получения регулярного выражения устранением состояний. Изложение не воспроизводит ни один учебник; происхождение каждого алгоритма названо при его описании локатором. РАЗГРАНИЧЕНИЕ С СОСЕДНИМИ ПАКЕТАМИ РЕПОЗИТОРИЯ НАЗВАНО ПРЯМО. Определения ДКА, НКА, регулярного выражения и теоремы о них — включая теорему о детерминизации и теорему Клини — закреплены пакетом `hws.regular_languages` по книге Critchlow & Eck; настоящее изложение их ПРИМЕНЯЕТ и не переустанавливает. Исполнимые построения над предъявленным автоматом — детерминизация, минимизация, автомат Томпсона, перевод в выражение — живут в вычислительном пакете `calc.regular_languages`. Настоящее изложение описывает УСТРОЙСТВО этих построений; оно не есть ни их определение, ни их реализация. Одно расхождение с вычислителем названо здесь отдельно и намеренно: минимизация в `calc.regular_languages` выполняется таблицей различимых пар, а настоящее изложение описывает алгоритм Хопкрофта. Это ДВА ВАРИАНТА одной задачи с одинаковым результатом и разными оценками; выдавать один за другой нельзя.