0

まず第一に、これが私が求めているものの正しい翻訳であるかどうかはわかりません。

私のコースの1つでは、正規表現や形式言語などについて学び始めました。

Alphabet {1,0,S,R}
Terminals {1,0}
Rules:

S ::= 0
S ::= 1
S ::= 1R
R ::= 1R
R ::= 0R
R ::= 1
R ::= 0

この場合、私が1Rから始めたとしましょう。そうすれば、1Rまたは0Rのどちらかを続けていくことができます。

1Rから始めると、1 ....すると、文（この場合は2進数）は完全になりますか？後で何かを「追加」できないので、1Rと言ってから、1を選択してから、もう一度1Rを選択しますか？

よろしくお願いします。正しくない場合は、投稿にタグを付け直してください。

追加した：

0  at rule S ::= 0  
1  with S ::= 1  
10 with S ::= 1R, so R ::= 0

1100110を生成する方法は？

これは宿題ではなく、パワーポイントからの例/質問です。それがどのように行われるのかわかりません。

4

3 に答える 3

3

あなたが持っているのは、文脈自由文法を使用して定義された正規言語です。同じ言語を定義する正規表現はです(0)U(1{0,1}*)。平易な英語では、正規言語には、1で始まる0と1のすべての文字列、および文字列0が含まれます。

文脈自由文法は、最初の非終端記号で始まります。この場合はSのように見えます。その後、リストされている生成規則に従って、非終端記号を記号の文字列に置き換えることができます。文字列に非終端記号が含まれていない場合は「完了」です。

あなたの例では、置換する文字列に現在SまたはRがある場合にのみ、「1Rを選択」できます。この文法で発生するように、初めてRを1に置き換えると、置き換える非終端記号がなくなり、文字列の生成が終了します。

編集：これは1100110の生産の痕跡です。

S  
1R         via S ::= 1R
11R        via R ::= 1R
110R       via R ::= 0R
1100R      via R ::= 0R
11001R     via R ::= 1R
110011R    via R ::= 1R
1100110    via R ::= 0
于 2011-02-14T18:42:02.797 に答える
2

あなたは正しいです。追加は許可されておらず、置換のみが許可されています。ただし、この言語では、「R ::=1R」または「R::= 0R」を選択し、もう一度Rに置き換えることで、文字列を継続的に長くすることができます。

于 2011-02-14T18:29:27.043 に答える
1

1Rから始めると、1 ....すると、文（この場合は2進数）は完全になりますか？

はい、これは正しいです。文11はS=1R=11に一致します。

ただし、この文法では、いつでもR=1RまたはR=0Rを使用して、文にさらに多くの数字を追加できます。

編集：質問の編集に応じて：

1100110を生成する方法は？

1100110 = S = 1R = 11R = 110R = 1100R = 11001R = 110011R = 1100110

それがあなたの理解に役立つことを願っています。

幸運を！

于 2011-02-14T18:31:03.403 に答える