regex - 将 NFA 转换为正则表达式并判断它是否是 3 的倍数？

Question

我正在练习，只是想确认我是否正确地做出了表达并将表达识别为 3 的倍数？

is that correct expression and my answer:
 ((aaa)* + (bbb)*) 
 expression shows a string length multiple of 3

Answer 1

是的，您的正则表达式是正确的，图中 NFA 定义的语言接受空字符串 ^ 或 (aaa) ⁺或 (bbb) ⁺。您已经在 * 闭包中覆盖了 ^。

如果您愿意，可以将其 DFA 设置为如下所示：

     __ bbb          __ aaa  
     ||              ||
     ▼|              ▼|
--►((Q0))---aaa---►((Q1))

其中 Q0 和 Q1 都是最终状态（Q0 是开始状态）。

旁注：您可以将“aaa”的边缘标签替换为“bbb”，将“bbb”替换为“aaa”，以获得另一种形式的相同 DFA。此外，在 DFA 的标准形式中，边缘标签可以是单一语言符号。