context-free-grammar - 与えられた言語から文脈自由文法を構築する

Question

特定の言語の CFG の作成についてサポートが必要です。

L = { x ∈ {a, b}* | x != x reversed }、つまり、Lは のすべての回文の補数ですL。

私は、特定の解決策よりも、この種の問題にどのようにアプローチするかに興味があります。

Answer 1

まあ、私はまだそのような問題を解決するための一般的なパターンを理解していませんでしたが、私はこの問題を解決する方法を知っていると思います：

まずG(L)、回文言語のCFGを検討しますL（バイナリアルファベットを検討しましょう）。

S -> ""
S -> "0" S "0"
S -> "1" S "1"
S -> "1" // odd length case
S -> "0" // odd length case

構築の考え方はG(L)、最後の記号がSの最初の記号と等しくなるようにすることです。したがって、すべての位置で、その文法によって生成された単語の最初からのth記号が最後からのth記号iとi等しくなります。i

回文ではない単語については、最初からのth記号が最後からのth記号と等しくないwような位置にあることを確認したいと思いiます。ですから、生産の最初と最後に異なる文字を入れた後でのみ、単語の生産を終了しましょう。ii

S -> "0" S "0"
S -> "1" S "1"
S -> "0" T "1"
S -> "1" T "0"
T -> ""
T -> "0" T "0"
T -> "1" T "1"
T -> "0" T "1" // we are allowed to put different symbols more than once
T -> "1" T "0" // we are allowed to put different symbols more than once
T -> "0"
T -> "1"

S状態の意味は「まだ別の文字を入れていません」、「別の文字を入れています」の意味を与えることができますT。このCFGでルールを削除S -> ""したので、からのみ終了することに注意してください。したがってT、単語を生成するときに必ず別の文字を入力します。