0

私は次の文法を扱っています：

G = ( {S, A}, {a, b}, P, S ) 
P = { S -> aAb, S -> bAa, 
A -> aSa, 
A -> S, 
A -> epsilon}

私は L(G) を見つける必要があります。問題は、文法の単語が次の形式であることがわかりました: a で始まり b で終わる、または b で始まり a で終わる、そしてこれらの文字の間の組み合わせの 1 つ: ab、ba、aaba、あばあ; 次の単語は、これらの 4 つの組み合わせのいずれかを真ん中の a と b の間に挿入することによって形成されます..しかし、これをどのように正式に表現できますか? つまり、私が知る限り、L(A) = a^n S a^n であり、w が L(G) に属している場合、w 反転も L(G) に属しています。正規表現として表現しようとしましたが失敗しました...誰か助けてもらえますか?

ありがとうございました。

4

4 に答える 4

1

L が正則でないことがわかります。これは、ポンピング レンマまたはMyhill-Nerode の定理を使用できることを証明するためです。そのため、正規表現については説明できません。

L は {a,b} だけで構成されているため、その力を利用できることがわかります

それではこれを使ってみましょう。唯一欠けているのは bAb の組み合わせです A はほとんどすべて (単語 |w| = 2k、および |w|>=2) を生成できますが、b の位置が b の位置と逆から一致する単語は

正式に ここに画像の説明を入力

私のテックススキルとフォーマルな表現でごめんなさい

これについて考える時間があまりなかったので、何らかのエラーがあるに違いありませんが、続行する方法はあるかもしれません。宿題なので大丈夫です。考えてみてください。:)

于 2011-11-14T20:21:48.127 に答える
0

文法Gによって生成された言語をプロダクションで見つけるように求められます

S → aAb | bAa
A → aSa | S | λ

最初に、開始記号Sから始まる小さな派生を考えます。

S ⇒1 aAb ⇒1 aaSab | aSb | ab

S ⇒1 bAa ⇒1 baSaa | bSa | ba

難しいステップは、規則A → aSa、S → aAb、およびS → bAaによって生成される再帰を処理することです。この困難に対処する手がかりは、Gによって生成される言語の帰納的な定義を検討することによって明らかになります。

1. ab ∈ L4
2. ba ∈ L4
3. w ∈ L4 → awb ∈ L4
4. w ∈ L4 → bwa ∈ L4
5. w ∈ L4 → awa ∈ L4

ルール (3)-(5) は、 G のルールA → aAa、S → aAb、およびS → bAaに対応します。帰納的な定義とGの規則が同じ言語を定義していることは容易にわかります。帰納的な定義は、Gの言語が段階的に段階的に構築できることを示しています。Gで生成可能な最小の文字列から始めて、問題のあるルールに対応するより大きな文字列セットを構築します。

L(1)     = {ab, ba}
L(n + 1) = {awb, bwa, awa : w ∈ L(n)}

セットL (1) には、 Gで生成可能な最小の文字列が含まれます。セットL (n + 1) には、各文字列w ∈ L (n)の文字列awb、bwa、およびawaが含まれます。つまり、L (n + 1) の文字列は、L (n) の文字列に規則S → aAb 、 S → bAa 、 A → aAaを1 回適用して得られる文字列に対応します。残っているのは、集合であるL (n)の和集合を構築することだけです。

L = ⋃ {L(n) : n ∈ ℕ}

Lが文法Gによって生成された言語と同等であることを確認するには、 Gの派生の長さに関する帰納法によって論じることができます。Gで分類可能な最小の文字列(つまり、abとba ) から始めて、適切な帰納仮説を使用して逆方向に作業します。

于 2011-11-22T16:33:14.603 に答える
0

生成される言語は次のとおりです: (a) n (b) m Were n>=m

于 2014-11-02T20:44:49.253 に答える
0

正規表現で表現しようとしましたが失敗しました

この言語は「おそらく」規則的ではありません。コンテキストフリー言語は、正規表現よりも複雑で強力です。

いくつかの単語を生成してみて、言語の名前やプロパティを思いつくことができるかどうかを確認してください。または、その言語にない単語を探してみてください。

いくつかのヒント、簡単に確認できるいくつかのプロパティ:

  1. 最小の文字列は少なくともサイズ 2 です。

  2. 文字列のサイズは均等です。

  3. b の数は a の数 <= です。

を取り出してA -> aSa単語を反転したものと比較すると、パターンが見えるはずです。左アウトルールを含めると、パターンが少し変わります...

于 2011-11-14T16:05:53.707 に答える