Минимальная длина регулярного выражения

Работа на мою домашнюю работу для класса, и я пришел на этот вопрос:Минимальная длина регулярного выражения

Для каждого из следующих регулярных выражений, дают минимальные строки длины, которые не на языке определяется выражением ,

(bb)*(aa)*b*
a*(bab)*∪b∪ab

Я буду стараться только получить помощь по первому и увидеть, если я могу понять, второе. Heres, что я знаю: Kleene * указывает 0 или более возможных элементов. и объединение множества - это множество, содержащее все элементы множества a и множество b без повторения элемента. Проработка первой задачи, начиная от введения лямбды, я получаю:

первого запуска: bbaab
вторым: bbbbaabaabbaabbbbaab
третьим: bbbbbbaabaabbaabbbbaabaabbbbaabaabbaabbbbaabbbbbbaabaabbaabbbbaab

Если я делаю что правильно, чем строки длины от 0 до 5 не находятся на языке. Правильно ли я делаю это?

источник

2012-02-15 user1193839

Подсказка: букв больше, чем 'a',' b' и 'U'. –

Первый случай может быть строкой нулевой длины. * означает 0 или более случаев, поэтому на самом деле, если вы используете пустую строку, это также нормально. –

Что вы имеете в виду, что есть больше букв, чем b и u? Я понимаю, что строка, обрабатывающая *, может быть любой возможной строкой, но в минимальном случае мы помещаем пустую строку λ вместо символа *, поэтому для генерируемой первой строки должно быть bb [λ] aa [λ] λ правильно? – user1193839

Первое регулярное выражение соответствует любому слову, начинающемуся с четного числа «b» (включая нуль), за которым следует четное число «a» (нуль в порядке), а затем некоторые «b».

Это означает, что пустая строка находится на языке, а также строка «b». Однако строка «a» отсутствует на языке.

Таким образом, вся строка минимальной длины, которая не находится на языке, является «a».

Второе выражение совпадает с «», «а» и «аа» (с помощью * (баб) *), а также на «б» и «AB». Однако он не соответствует «ba» и «bb».

Таким образом, минимальные строки имеют длину 2: «bb» и «ba».

источник

2012-02-15 06:17:02

Вы неправильно читаете его, потому что OP не форматирует его хорошо. После издания регулярное выражение равно '(bb) * (aa) * b *' not '(bb) * aab'. – Benoit

Да, спасибо, я обновил ответ :) –

Упрощенное второе регулярное выражение - это * bab + b + ab, поэтому это слово начинается с некоторого количества a, включая 0, за которым следует bab * (который также может быть нулевая строка), поэтому его возможно, если нулевая строка находится в языке, потому что λ ∪ λ ∪ λ = λ. Я смущен тем, что делает профсоюз, хотя пустая строка не используется. Почему dont bb и ba работают во втором? – user1193839

Минимальная длина регулярного выражения

ответ

Смежные вопросы