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

12

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

Например, мне сказали, что если бы я мог использовать только операции регулярного выражения объединения и объединения (2 из 3), был бы обычный язык, который я не могу описать только этими двумя.

То же самое только со звездой Клини и Юнионом. Каковы некоторые примеры этого?

user3295674
источник

Ответы:

19

Только с объединением и объединением вы не можете описать любой бесконечный язык. Объединение и объединение могут создавать только конечное число строк. Только с объединением и звездой Клини вы не можете описать такой язык, как , потому что нет способа объединить выражение, генерирующее только a, с выражением, генерирующим только b . Только с конкатенацией и звездой Клини вы не можете описать такой язык, как L = { a , b } .L={ab}abL={a,b}

DylanSp
источник
3
{a,b}
Так почему я не могу описать L = {a, b} без объединения? Это потому, что они не могут быть представлены как отдельные элементы со звездой и конкатенацией? Это могли делать только ab, bb, aba и т. Д.?
user3295674
@ user3295674 Точно.
DylanSp
и что-то вроде L = {a *} было бы невозможно только с помощью объединения и объединения, верно? Спасибо огромное!
user3295674
Я даже не понимаю, как звезда будет определена без конкатенации.
Г. Бах
11

(abc)dddd1

Юваль Фильмус
источник
4

A(ab)(a(ab)b)(aa)

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

J.-E. Штырь
источник