Dafny 我如何编写谓词来证明字符串按 'b' => 'a' => 'd' 排序？

Question

有人可以帮我写一个 Dafny 谓词来检查字符串是否按顺序排序 'b' -> 'a' -> 'd'

即：

“bbbaaaaad”== 真
“abd”==假
“坏”== 真

谓词应具有以下形式：

predicate sortedbad(s:string) 
{
[???]
}

谢谢

Answer 1

这是一种方法。

predicate bad_compare(c1:char, c2:char) {
  c1 == 'b' || (c1 == 'a' && c2 != 'b') || c2 == 'd'
}

predicate sortedbad(s:string) 
{
  forall i, j | 0 <= i <= j < |s| :: bad_compare(s[i], s[j])
}

lemma Test()
{
  assert sortedbad("bbbbaaaadddd");
  var s := "bbbbbbda";
  assert !bad_compare(s[6], s[7]);
  assert !sortedbad(s);
}

Dafny 我如何编写谓词来证明字符串按 'b' => 'a' => 'd' 排序？

Dafny How could I write a predicate to prove a string is sorted by 'b' => 'a' => 'd'?

dafny