2

次の言語の文脈自由文法を構築するにはどうすればよいですか。

L = {a^l b^m c^n d^p   | l+n==m+p; l,m,n,p >=1}

私は次のことを試みることから始めました：

S -> abcd | aAbBcd | abcCdD | aAbcdD | AabBcCd

そしてA=何か他のもの...しかし私はこれを機能させることができませんでした。

。

ノーのために何個のcのシャッドが増加したかをどうやって思い出すことができるのだろうかと思っていました。bの増加？
例えば：

string : abbccd
4

2 に答える 2

2

これはどうですか：

S1 -> a S2 d                   # at least one a and d
S2 -> a S2 d
S2 -> S3 S4                    # no more d, split into ab and bc parts
S2 -> S4 S5                    # no more a, split into bc and cd parts

S3 -> a S3 b
S3 ->                          # already ensured at least one a and b
S4 -> b S4 c                  
S4 -> b c                      # at least one b and c
S5 -> c S5 d   
S5 ->                          # already ensured at least one c and d

これの鍵は、グループ化する方法です...（つまり、非終端記号ではなく「パーツ」）。

于 2012-10-17T12:29:22.503 に答える
2

文法は：

  1. S1- > S1 d | S2

  2. S2- > S3 S4

  3. S3- > a S3 b | イプシロン

  4. S4- > S5 S6

  5. S5- > b S5 c | イプシロン

  6. S6- > c S6 d | イプシロン

ルール1は、同数のaとdを追加します。

ルール3は、同数のaとbを追加します。

ルール5は、同数のbとcを追加します。

ルール6は、同数のcとdを追加します

ルールはまた、アルファベットの順序が与えられた言語に従って維持されることを保証します。

于 2014-05-05T17:33:27.447 に答える