Теория формального языка (регулярные выражения и регулярные языки) - понятие «ИЛИ»

Question

Хорошо, поэтому при программировании логического символа ИЛИ (обычно ||) применительно к операндам a и b, то есть a || b означает, что либо a, либо b могут быть истинными, ИЛИ оба могут быть истинными. Если вы хотите, чтобы только один был истинным, вы используете XOR (иногда символ ^).

Однако в теории формального языка концепция ИЛИ (обычно символа +), по-видимому, подразумевает исключающее-или (xor) вместо обычного ИЛИ. Например, если мы опишем язык L с помощью регулярного выражения aa + bb + ab, допустимая строка (слово) из языка будет одной из этих (aa, bb или ab), а не какой-либо их конкатенацией. Чтобы сделать это, вы должны использовать замыкание Клини, как в (aa + bb + ab) *, верно?

Возможно, я просто думаю о + как об определенном смысле, или, может быть, операнды больше не являются булевыми?

Я просто ищу подтверждение, если мне кажется, что + (ИЛИ) имеет, по-видимому, другое значение в формальном языке / вычислительном моделировании, чем в языках программирования. Спасибо!

Answer 1

Проблема не в операторе - + в регулярных выражениях действительно означает то же самое, что и объединение множеств - проблема в том, как вы понимаете операнды. В частности, в вашем регулярном выражении aa + bb + ab, aa не представляет строку над вашим алфавитом, а является субрегулярным выражением. Регулярные выражения описывают наборы строк; поэтому регулярное выражение aa описывает множество строк {aa}. Итак, регулярное выражение aa + bb + ab описывает множество строк {aa} union {bb} union {ab} = {aa, bb, ab}. Симметрическое различие в теории исключений или теории множеств не имеет оператора в синтаксисе регулярных выражений. Мы можем рекурсивно определить язык регулярного выражения, написанного L (r) для регулярного выражения r, следующим образом:

• L (r) = {r}, если r - строка над алфавитом;
• L (r) = L (s) L (t), если r = st;
• L (r) = L (s) *, если r = s *;
• L (r) = L (s) объединение L (t), если r = s + t.

Answer 2

Формальным языком ИЛИ является включительно («обычный») ИЛИ. Например, обычный язык ab* + a*b включает в себя строки, которые имеют как ab*, так и a*b (т.е. строка ab).