1

我应该将线性右语法转换为有限状态机。语法是

S —> bA|aD|bC
А —> aC|bA
C —> bB|aA|b
B —> aD|bC|a
D —> aA|aC

通常问题是这样解决的：我们将非终结符关联到每个状态。如果状态存在从 X 到 Y 的转换，我们添加规则 X → aY。添加最终状态规则 X → ε。对于 ε-跃迁 - X → Y。

例如：

A → aB | cC
B → bD | cE
C → ε
D → aB | cC
E → aB | cC

解决方案

问题。

  1. 如果有连接A和A怎么办，例如A -> aC | 乙。
  2. 如何处理结构 C -> bB | AA | b，结尾只有 b。
4

1 回答 1

2

1]你可以做自循环（例如节点Z可以添加字母o然后去节点Z）

2]使用陷阱状态。您不能从那里移动到任何地方，但仍然需要移动（因此需要一封信）才能到达那里

于 2013-06-06T19:16:09.750 回答