6

アルファベット{a、b}で次の正規表現の言語を見つけるにはどうすればよいですか？

aUb*
(ab*Uc)
ab*Ubc*
a*bc*Uac

編集：私が狂ったように反対票を投じる前に、誰かが解決策だけでなく、これらの問題を解決するためのステップを教えてくれれば幸いです。たぶん、私が自分で残りを行うことができるように、私を1つに案内することさえあります。

ありがとう！

4

3 に答える 3

6

編集：短い答えは*、ほとんどすべての正規表現/文法構文で「ゼロ以上の繰り返し」を意味します。perl5とRFC 5234が含まれます。 *通常、連結や交互変換よりも緊密にバインドされます。

あなたはアルファベット（a、b）よりも言語が欲しいと言いますが、表現にとを含めcますU。perl reUと同様に、が低優先順位の和集合演算子である正規表現が与えられたBNFのような形式で、アルファベット（a、b、c）よりも言語文法が必要であると想定します。|

その場合、

a|b*

BNFと同等です：

L := a
   | <M>
M := epsilon
   | b <M>

*演算子は0以上を意味するため、の最初の句は基本ケースであり、2番目の句は端末を含むM再帰的な使用です。Mb

Lは、単一a終端記号または非終端記号のいずれかMです。

(ab*|c)

L ::= a <M>
    | c
M ::= epsilon
    | b <M>

Mは上記と同じ方法で導出され、残りは自明です。

ab*|bc*

L ::= a <M>
    | b <N>
M ::= epsilon
    | b <M>
N ::= epsilon
    | c <N>

Nは、上記のMと同じ方法で導出されます。

a*bc*|ac

ほとんどの*正規表現言語では、連結よりも緊密に結合するため、これは次のようになります。

(a*b(c*))|(ac)

要約すると

L ::= <M> b <N>
    | a c
M ::= epsilon
    | a <M>
N ::= epsilon
    | c <N>

一般に、正規表現をBNFに変換するには、正規表現で隣接関係を使用してBNFでアジャセニーを意味するUか|、正規表現|でBNFを意味します。

非終端記号を定義すると、次のよう<X> ::= xに処理x*できます。

L ::= epsilon
    | <X> <L>

同じ非終端記号<X> ::= xを使用すると、次のように処理x+できます。

L ::= <X>
    | <L> <X>

それはあなたに繰り返し演算子*を取得し、それは+を残し?ます。 x?単に

L ::= epsilon
    | <X>
于 2011-10-03T04:13:14.140 に答える
2

マイクは正規表現で示される言語を生成する文法を与えましたが、あなたの割り当ては言語自体を要求します。正規表現を扱っているので、答えは正規表現でなければなりません。

アルファベット上の通常のセットの定義を思い出してください。

Let Σ be an alphabet. The class of regular sets over Σ is the smallest class
containing ∅, {λ}, and {a}, for all a ∈ Σ, and closed under union, concatenation,
and Kleene star.

ここで、アルファベット上の正規表現の定義を思い出してください。

Let Σ be an alphabet. The class of regular expressions over Σ is the smallest
class containing ∅, λ, and a, for all a ∈ Σ, and closed under union, concat-
enation, and Kleene star.

したがって、翻訳は簡単なはずです。実際、それは各文字の周りに中括弧を挿入することで構成されています！例えば：

a ∪ b*  denotes {a} ∪ {b}*
ab* ∪ c denotes {a}{b}* ∪ {c}
...

各正規表現の言語を集合の内包的記法で表現したい場合は、正規表現に対する操作の定義に戻すことができます。想起：

Let A and B be regular sets. Then
   1  A ∪ B = {x : x ∈ A ∨ x ∈ B}
   2. AB    = {xy : x ∈ A ∧ y ∈ B}
   3. A*    = ∪[i = 0 -> ∞]A^i

通常のセットは、通常のセット操作の定義を置き換えることにより、セットビルダー表記に変換できます。ネストされた集合の内包的記法の導入を避けるために、連結の定義と組み合わせて等式を使用して、通常の集合の連結を表現しました。

{a} ∪ {b}*    = {w : w ∈ {a} ∨ w ∈ ∪[i = 0 -> ∞]{b}^i}
{a}{b}* ∪ {c} = {w : (w = xy ∧ (x ∈ {a} ∧ y ∈ ∪[i = 0 -> ∞]{b}^i)) ∨ w ∈ {c}}
...

これで、残りの式で示される言語を問題なく見つけることができるはずです。

于 2011-10-04T07:43:20.077 に答える
1

スター、ユニオン、および連結の意味を知っている場合、これらは簡単なはずです。1つ目はユニオンbスターです。演算の順序によると、これは和集合（bスター）を意味します。ユニオンとは、左側の言語のすべて、または右側の言語のすべてを意味します。aは、長さ1つの文字列aで構成される言語を意味します。bスターとは、0個以上のb記号だけで構成される任意の文字列で構成される言語を意味します。したがって、この言語は{empty、a、b、bb、bbb、bbbb、...}です。2番目の場合、ab *は、aの後に0個以上のb記号が続くすべての文字列を意味します。与えられた明示的な括弧に従って、最初にスターを付け、次に連結、次に和集合を実行します。

于 2011-10-03T04:20:09.427 に答える