如何在 Dafny 中定义这种正则语言？

Question

《自动机理论与应用》一书中有道题是讲语言的

如何在 Dafny 中定义这样的语言？

Answer 1

这是将 L 的定义直接转录成 Dafny。

predicate ContainsOnlyAsAndBs(s: string)
{
  forall c | c in s :: c == 'a' || c == 'b'
}

predicate L(w: string)
  requires ContainsOnlyAsAndBs(w)
{
  exists x | ContainsOnlyAsAndBs(x) && x != [] :: w == ['a'] + x + ['a']
}

请注意，在 Dafny 中，类型 string 被定义为 seq<char>。所以我们可以使用通常的 built-in 方法来操作字符串上的序列。