寻找识别 { a^i b^j b^i a^j | 的文法或下推自动机我, j >= 0 }
Finding a grammar or a pushdown automaton that recognizes { a^i b^j b^i a^j | i,j >= 0 }
我正在尝试寻找识别以下语言的语法或下推自动机：
{ ai bj bi aj | i,j >= 0 }
在我看过的所有示例中，我无法理解这个！
我首先尝试使用语法，因为我认为这可能更容易递归，然后是下推自动机，但没有成功。我不知道如何处理 ai 和 bi 之间的 bj .
正如i + j = j + i, b<sup>i</sup>b<sup>j</sup> = b<sup>j </sup>b<sup>i</sup>。换句话说，两个b是没有区别的。
也许你会发现更容易看到 { a<sup>i</sup>b<sup>i</sup>b[=16 的语法=]j</sup>a<sup>j</sup> | i,j ≥ 0 }
我正在尝试寻找识别以下语言的语法或下推自动机：
{ ai bj bi aj | i,j >= 0 }
在我看过的所有示例中，我无法理解这个！
我首先尝试使用语法，因为我认为这可能更容易递归，然后是下推自动机，但没有成功。我不知道如何处理 ai 和 bi 之间的 bj .
正如i + j = j + i, b<sup>i</sup>b<sup>j</sup> = b<sup>j </sup>b<sup>i</sup>。换句话说，两个b是没有区别的。
也许你会发现更容易看到 { a<sup>i</sup>b<sup>i</sup>b[=16 的语法=]j</sup>a<sup>j</sup> | i,j ≥ 0 }