Русскоязычное программирование (План А)

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.



Вычитание регэкспов

Сообщений 1 страница 3 из 3

1

http://rsdn.org/forum/alg/3979361.all

Пусть L(a) обозначает язык автомата A, т.е. то множество цепочек, которое этим автоматов допускается.

Исходная задача сводится к двум:

1. Для автомата B получить автомат, который допускает -L(B), т.е. дополнение языка L(B). Эта задача стандартная, надо просто инвертировать состояния исходного автомата: каждое допускающее сделать недопускающим, а каждое недопускающее -- допускающим. Тогда, любая цепочка, которая недопускается автоматом B, станет допускаться автмоматом -B. с другой стороны, если цепочка допускается автоматом B, то при ее чтении он переходит в недопускающее состояние, а значит, в недоспускающее состояние автомата -B. Иначе говоря, дополнение автматного языка является автоматным языком.

2. Найти автомат, который допускает пересечение языков автоматов A и -B. Основная идея такого автомата -- это запуск параллельно двух автоматов и допуск цепочки только тогда, когда автматы при чтении цепочки одновременно переходят в допускающие состояния. Но понятие "параллельно" в контексте автоматов и их языков непонятно, надо сконструировать новый автомат, который инкапсулирует идею параллельного запуска в себе. Для этого вводят автомат, который работает не на одной цепочке, а на цепочке из пар символов. Пара в данном случае обозначает как раз, что автоматы запускаются на двух цепочках одновременно. Пары -- это декартово произведение, т.е. мы берем цепочки над алфавитом Sigma(A) X Sigma(B), где Sigma(A) и Sigma(B) -- алфавиты языков соответствующих автоматов. Состояния автомата -- пары состояний исходных автоматов, допускающие из них -- пары из допускающих состояний. На вход этому автомату подается последовательность пар символов, но нам необходимо выполнить требование, что пары в этой цепочке должны формироваться из одних и тех же символов, тогда это будет соответстовать нашей идее запуска двух автоматов на одной цепочке. Т.е. из всех пар мы должны выбрать только те, у которых первый и второй компоненты равны, т.е. диагональ декартова произведения. Эта самая диагональ есть то же самое, что и сама цепочка.

Отредактировано Лис (2017-10-05 17:41:23)

0

2

Неожиданное применение:

Бывают разные там направленные ациклические графы (например файловые системы с симлинками и прочими линками).
а может и не файлы, а так называемые "системы" в великом дереве

Множество файлов можно выбирать при помощи разновидности регулярных выражений - масок (globs). Для этого есть спецсимволы * и ?
Регулярные выражения могут быть двух видов - учитывать файлы (include) и не учитывать файлы (exclude).
В результирующее множество файлов должны попасть только те файлы, которые удовлетворяют условиям include и не подходят под условия exclude.

Нужно строить результирующее множество таким образом, чтобы не связываться с узлами, входящими в exclude-множество, так как некоторые из таких узлов могут обладать неприятными особенностями (например иметь слишком длинный путь. Да и вообще файловая система не ациклическая, а вполне циклы может содержать)

по русски это "упрощение математических выражений"

Отредактировано Лис (2017-10-05 17:25:46)

0

3

а так называемые "системы" в великом дереве

Системы это всего лишь способ представления окружающего мира. Кто-то бухает, кто-то употребляет вещества, кто-то позволяет вешать себе лапшу на уши религиозным деятелям, а кто-то представляет мир как луковицу, где каждый слой система :). Иггдрасиль https://ru.wikipedia.org/wiki/Иггдрасиль хорошая штука.

Да и вообще файловая система не ациклическая, а вполне циклы может содержать)

Это рекурсия выраженная во фрактале. Цикл это процесс, он не совсем годится для описания состояния (файловой системы например). Это способ придти к такому состоянию. А фракталы (или фрагменты с их участием) это состояние, результат (рекурсии или цикла). Использование термина цикл в графах как раз связано именно с описанием процесса (следования от узла к узлу).

Отредактировано utkin (2017-10-06 08:06:17)

0