这个语法正规吗？

Question

这个语法正规吗？如果是，那么正则表达式是什么？

S-> aAa|ε A-> abS|c

我认为它是规则的，所以我确实认为它是规则的，我的表达式是 (a^2b)^(aca+epsilon)a^

这样对吗？

提前致谢。

Answer 1

为了判断给定的语法是否是正则，我们需要分析产生式规则：

S→aAa∣ϵS→aAa∣ϵ
A→abS∣cA→abS∣c

常规语法特征

如果满足以下条件，则语法是正规的：

The right-hand side of production rules has at most one non-terminal, and it should appear at the right end.
It can also have only terminals, or a single terminal followed by a non-terminal.

现在我们来分析一下每一个作品：

S→aAaS→aAa and S→ϵS→ϵ:
    S→ϵS→ϵ is fine for a regular grammar (allowing empty strings).
    S→aAaS→aAa is problematic because it has a non-terminal AA surrounded by terminals, which isn't allowed in regular grammars.
A→abSA→abS and A→cA→c:
    A→cA→c is fine as it has only a terminal.
    A→abSA→abS isn't regular because it has two terminals followed by a non-terminal, which violates the regular grammar rules.

结论

由于不合格产生式 S→aAaS→aAa 和 A→abSA→abS，提供的语法不规则。 正则表达式注意事项

由于语法不是正则的，我们不能直接从中导出正则表达式。然而，如果我们简化语法，或者如果我们被要求找到由该语法的正则子集描述的语言的正则表达式，我们可以采取不同的方式。

您尝试的正则表达式 (a2b)aca+ϵa(a2b)aca+ϵa 似乎旨在捕获一些模式，但不符合语法语言的非正则性质。