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

これは、手動検査について考える方法を示しています。アルゴリズムによる解決策は別の質問であり、率直に言って、あなたが求められたように聞こえるものではありません。