Я думал, что все регулярные языки могут быть выражены с помощью регулярных выражений (если язык регулярный, он может быть выражен с помощью регулярных выражений), но мне сказали, что для этого вам нужны все три регулярные операции (конкатенация, объединение и звездочка) держать.
Например, мне сказали, что если бы я мог использовать только операции регулярного выражения объединения и объединения (2 из 3), был бы обычный язык, который я не могу описать только этими двумя.
То же самое только со звездой Клини и Юнионом. Каковы некоторые примеры этого?
источник
Если сейчас разрешено использовать звезду, но не вложенные звезды, тогда остается открытой проблемой (не менее 45 лет) узнать, можно ли получить все обычные языки. Этот вопрос известен как обобщенная проблема высоты звезды . Это похоже на проблему с высотой звезды, упомянутую Ювалом Фильмусом, с той разницей, что дополнение теперь разрешено.
источник