3

そんなものはありますか？

たとえば、S-> aSb | ^（可能な単語：^、ab、aabb、aaabbb、aaaabbbb、...）

私が学んだことから、前述の文法に厳密に一致する唯一の正規表現は次のとおりです。a * b *

ただし、正規表現では、aab、abb、...などの単語を生成できます。ここで、aとbは等しくありません。

これに対する解決策はありますか？次のようなもの：a * b * if #a = #b

編集：私はこれに対する解決策はないと思います。

これの正しい説明は何ですか？これは実際には私の宿題の抜粋であり、文法を正規表現に翻訳する解決策がないため、私は本当に何に答えるべきかわかりません。

4

2 に答える 2

4

正式な言語理論について話している場合、もちろん、すべての非正規文法（例のように）を正規表現で表現することはできません（定義ごと）。

しかし、(プログラミング言語/正規表現ライブラリの) さまざまな正規表現フレーバーで何ができるのか疑問に思っている場合は、すべての種類の非正規文法/言語に一致させることができます。

たとえば、Perl/PCRE では、サンプル言語を次のいずれかと一致させることができます。

  • 再帰/サブパターン呼び出しの使用:

    ^(a(?1)b)$

  • 後方参照の使用 (条件付き):

    ^(?:a(?=a*(b(?(1)\1))))+\1$|^$

この質問と回答に興味があるかもしれません:正規表現 (PCRE) を使用して a^nb^nc^n (例: "aaabbbccc") に一致させます。

于 2013-02-05T17:42:10.773 に答える
0

形式言語理論では、「ポンピング補題」と呼ばれるものを使用して、特定の文 (言語) のセットが正規表現で記述できないことを証明できます。ウィキペディアhttp://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languagesを参照してください。記述したい言語から始めて、ポンピング補題を使用して矛盾を見つけます。あなたの例の証拠は、実際にはそのウィキペディアのページにあります。

文脈自由言語にも同様の理論が存在します。一部の言語は、文脈自由文法では記述できません。

于 2013-05-24T18:20:32.897 に答える