0

文脈自由文法を使用して、有限言語または無限言語の解決策を考え出そうとしています。

私はこれらの文法を持っており、それが有限または無限の言語の解であるかどうかを見つけます

S -> XY|bb  Step 1
X -> XY|SS  Step 2
Y -> XY|SS  Step 3

だから私はするだろう

S -> XY            From step 1
S -> YYY           From step 2
S -> SSYY          From step 3
S -> SSSSY         From step 3
S -> SSSSSS        From step 3
S -> bbSSSSS       From step 1
S -> bbbbSSS       From step 1
S -> bbbbbbSSS     From step 1
S -> bbbbbbbbSS    From step 1
S -> bbbbbbbbbbS   From step 1
S -> bbbbbbbbbbbb  From step 1

bbbbbbbbbbbb

だから私はここでこのような単語を生成する方法を知っていますが、それが有限言語か無限言語かをどのように見つけるのでしょうか?

4

1 に答える 1

1

S が何かとそれ自身に向かうことを示すことができれば、たとえば S->bS のように、あなたの言語は無限です。誰かがその言語が表すことができるすべての有限リストを作成しようとした場合、その有限リストのどの文字よりも 1 文字長いものをいつでも合法的に作成できます。したがって、有限リストは実際には言語が生成できるすべての完全なリストではなく、言語は無限です。

于 2014-04-02T20:48:18.307 に答える