1

通常の言語を表現するには正規表現を使用し、文脈自由言語にはスタックのようなメモリを使用できます。文脈自由言語には中央埋め込みなどの仕様があることは知っていますが、特定の言語が文脈であるといつ確信できるかはまだわかりません自由語？たとえば、なぜ自然言語は通常の言語ではないのでしょうか。センター埋め込み以外に理由はありますか？

4

1 に答える 1

0

オートマトン理論では、通常の言語は有限状態機械 (FSM) で処理できるとされています。ただし、言語に「中央埋め込み」がある場合、その言語はプッシュダウン オートマトン (PDA) を必要とするコンテキスト フリー言語 (CFL ) です。

重要なことに、PDA は、埋め込みを追跡するために「スタック」または「カウンター」であるメモリのようなデバイスの追加リソースを備えた FSM です。

ウィキペディアは、コンテキストフリーではない言語で次のように述べています:-

与えられた言語が文脈自由でないことを証明するために、 the pumping lemma文脈自由言語または や などの他の多くの方法をOgden's lemma採用することができますParikh's theorem。

ウィキペディアは、言語が正規かどうかを決定するで述べています:-

言語が規則的でないことを証明するために、他の方法の中でもとりわけ Myhill-Nerode の定理またはポンピング補題がよく使用されます。

なぜ自然言語は正規言語ではないのですか?

チョムスキーは (1957) で次のように述べています。「英語は正規言語ではない」. 文脈自由言語については、「英語自体が文字通りそのような分析の範囲外であるかどうかはわかりません」。

私はそれを追加していEnglish is such a vast language which can't be recognised by a finite machineます。

于 2015-05-30T05:32:49.763 に答える