0

我不明白 PDA 图中的箭头...

我有一个 PDA，它接受所有带有嵌套的括号的字符串，如((((())))),(())等((()))。它有两个状态，第一个状态有一个循环的箭头，它的行为被描述为(,ε/(。

就我所见，(如果堆栈顶部有 ε，则此描述将接受符号，如果有，ε则将替换为(。

因此，如果堆栈一开始看起来像这样：
ε

现在看起来像这样：
(ε

(即使ε不再位于堆栈顶部，如何让这个循环箭头继续接受每个符号？

4

1 回答 1

1

对于该状态，您需要另一种行为： (, (->( 此转换应将您带到另一个状态（辅​​助状态）。该辅助状态的唯一转换是 ε, ε->(

从您的原始状态，您需要弹出（当您看到 a 时从堆栈中弹出）），（->ε

这是我的一个类似示例，其中 a 比 b 多（问题编号 1）在此处输入图像描述

于 2014-04-01T19:16:24.913 回答