0

私は理解するように求めるこの質問を受け取りました"Why is it foolish to write a regular expression for the language that consists of strings of 0's and 1's that are palindromes?"（彼らは同じように前後に読みます）。

質問のパート2は、"using any formal mechanism of your choice, show how it is possible to express the language that consists of strings of 0's and 1's that are palindromes."

4

2 に答える 2

1

ヒント: 正規表現はどのような言語を解析するように設計されていますか?

これは宿題の質問なので、完全な答えを提供するつもりはありません。完全な答えを自分で見つけ出すことで、より多くのことを学ぶことができます。もちろん、あなたの教育機関が持っている学術的な倫理規定におそらく準拠していることは言うまでもありません. ;)

于 2010-04-25T01:36:30.087 に答える
1

あなたが記述した言語の非正則性を証明する必要があります。これを行うには多くの方法がありますが、ここでは1 つの方法へのリンクを示します。

ポンピング補題まで下にスクロールします。これは、その証明手法を使用すると非常に簡単です。

ヒント: 言語がバイナリ回文を認識できる場合、言語は を認識でき101, 11011, 1110111, ...ます。

于 2010-04-25T01:41:52.663 に答える