形式语言理论（正则表达式和常规语言） - “OR”的概念

Question

好的，所以在编写逻辑OR符号（通常是||）时应用于操作数a和b，即|| b，表示a或b可以为真，或者两者都可以为真。如果只想要一个为真，则使用XOR（有时为^符号）。

然而，在形式语言理论中，OR的概念（通常是+符号）似乎意味着排他性或（xor）而不是常规OR。例如，如果我们用正则表达式aa + bb + ab描述语言L，则语言中的有效字符串（单词）将是其中一个（aa，bb或ab），而不是它们的某些串联。要做到这一点，你必须使用Kleene闭包，如（aa + bb + ab）*，对吧？

也许我只是认为+是以一种特殊的方式定义的，或者也许是操作数不再是布尔值？

我只是在寻找验证，如果我似乎理解+（OR）在形式语言/计算建模中具有与在编程语言中看起来不同的含义。谢谢！

Answer 1

正式语言OR是包含（“常规”）OR。例如，常规语言ab* + a*b包括ab*和a*b中的字符串（即字符串ab）。

Answer 2

问题不在于运算符 - 正则表达式中的+实际上意味着与集合的结合相同 - 问题在于您对操作数的理解。具体来说，在正则表达式中，aa + bb + ab，aa不表示字母表上的字符串，而是表示子正则表达式。正则表达式描述字符串集;所以正则表达式aa描述了字符串{aa}的集合。因此，正则表达式aa + bb + ab描述了字符串集合{aa} union {bb} union {ab} = {aa，bb，ab}。独立或集合论，对称差异，在正则表达式语法中没有运算符。我们可以递归地定义正则表达式的语言，为正则表达式r写成L（r），如下所示：

• L（r）= {r}，如果r是字母表上的字符串;
• 如果r = st，则L（r）= L（s）L（t）;
• L（r）= L（s）*如果r = s *;
• 如果r = s + t，则L（r）= L（s）并联L（t）。