1 
G={ {S,A} , {a} , {S -> SAS | a , A -> aS | a} ,S}

回答セクションでは、次のように書かれています。

L(G) = {a, a3, a4, a6, a7} と

L(G) の補数は次のように記述されます 。{a2, a5, a8, ...}

上記の言語とその補語がどのように生成されるかを理解するのを手伝ってください。

私の試み/分析：

上記の文法の文字列は、少なくとも 3 つの a (いいえ?) である必要S-> SASがS --> aありA --> aますS --> aaa。しかし、解決策L(G)は から始まりaます。

この概念を理解するのを手伝ってください。または、何か間違っていると解釈しています。

また、文法から言語を理解するための標準的なアプローチがあることを説明してください。私はたくさんグーグルで調べましたが、一般的な手順を見つけることができませんでした。前もって感謝します。PS-次の競争試験の準備をしています。

4

1 に答える 1

-1

次の文法 G の場合: 

G = {{S, A}, {a}, {S -> SAS | a, A -> aS | a}, S}

言語：

L(G) = {a, a3, a4, a6, a7}は正しく ありません。

5弦も可能です。

a製作があるので可能ですS --> a、

S-プロダクションは

S --> SAS 
S --> a

そして、Aプロダクションは 

A --> a
A --> aS

L(G) のすべての文字列は から生成されSます。センテンシャル形式をセンテンスに変換するには、または(奇数長 1) のいずれA --> aかを適用する必要があります。S --> a

文法から言語を理解するための巧妙なアプローチは、「ツリーを順番に生成する」ことです。:

w2 つ以上の長さの文字列を生成する|w| > 1には、プロダクション ルールを使用する必要がありますS --> SAS。 

    T1:            T2:

     s             S
    /|\           /|\
   / | \         / | \  
  S  A  S       S  A  S 
  |  |  |      /  / \  \
  a  a  a     a  |   |  a
                 a   a

4の次に可能な最小の文字列は5のみです。 

    T3:  

     s             
    /|\           
   / | \         
  S  A   s       
 /  / \  |\
a  |   | a \
   a   a    a

したがって、の褒め言葉 に5を使用することはできません。L(G)

編集：

8のアイデア: 

     T4:          

     s             
    /|\           
   / | \         
  S  A   S       
 /  / \   \
a  |   |   \
   a   a    T2

3a秒 + aT2 からの 5 秒 = 8a秒

文法の言語:

L(G)= は { | どこ} ann != 2

L(G)の補完はこれ{aa}だけ！

于 2013-01-03T14:18:36.187 に答える