grammar - 可能的最短字符串

Question

我在接受采访时，被要求给出给定这种上下文无关语法生成的最短字符串。我多年没有复习，所以我认为我错了。答案是什么，所以我知道它以供将来使用？

S --> ABA | SS
A --> S0  | T1T
B --> S1  | 0
T --> 0

Answer 1

通过检查，该语言中的最短字符串导出如下：

S
=> ABA      // SS can only be worse than S, no reason to take that route
=> T1TBT1T  // S0 can only be worse than T1T, since S0 will necessarily add more A
=> 0100010  // choosing a single terminal is always as good as we can do

这向您展示了如何考虑手动检查。算法解决方案是一个单独的问题，坦率地说，不是你被要求做的事情。