regex - 是a^i^2 | i>=1 常规？

Question

虽然这个表达式被确定性有限自动化所接受，但是如果我们在这个表达式上应用抽引引理，抽引引理会失败，这个表达式也有有限状态但不会停止并连续运行，边缘会继续产生自循环 b/w当 i 趋于变大并且趋于无穷大时，它不应该停止。因此，对于这个表达式，可以绘制 DFA，但抽取引理和 TM 失败。那么，告诉这是否是常规语法？

Answer 1

实际上无法绘制 DFA（至少是正确的）。你是对的，抽引引理给出了一个矛盾，很容易将i向上或向下抽动以使其非正方形。如果抽水引理表明一种语言不规则，那么根据定义，就无法绘制 DFA 来表示该语言。

状态集是无限的，必须有一个状态接受 a^1，一个接受 a^2，一个接受 a^3，依此类推。然后是这些接受状态之间的所有状态......它很快就会变得混乱。无论如何，如果泵引理显示一种语言不规则（假设您正确应用它），那么就没有 DFA（或正则表达式）来表示该语言。