問題タブ [regular-language]

計算理論のコースのメモをいくつか見直していますが、次のステートメントを表示するのに少し行き詰まっており、誰かが説明を手伝ってくれることを望んでいました:)

A を正規言語とする。言語 B = {ab | a は A に存在し、b は A に存在しない*} なぜ B は正規言語なのですか?

いくつかの点は私には明らかです。b が単なる定数文字列である場合、これは自明です。a が A にあり、b が文字列であることはわかっているため、通常の言語は和集合の下で閉じられているため、これら 2 つの文字列を受け入れる言語の和集合は明らかに規則的です。ただし、 b が定数であるかどうかはわかりません。そうかもしれませんし、もしそうなら、これは実際には問題ではありません。意味が分からなくて困っています。ありがとう！

ほとんどの UNIX 正規表現には、通常の**, +,?*演算子の他に、最後の括弧内のものと一致するバックスラッシュ演算子がある\1,\2,...ため、たとえば*L=(a*)b\1*(非正規の) language と一致します*a^n b a^n*。

一方で、スタックオートマトンでも認識できない(a*)b\1b\1言語に合わせて作成できるため、これはかなり強力に思えます。*a^n b a^n b a^n*一方で、*a^n b^n*このように表現することはできないと確信しています。

2 つの質問があります。

1. この言語ファミリーに関する文献はありますか (UNIX-y レギュラー)。特に、これらのポンピング補題のバージョンはありますか?
2. *a^n b^n*このように表現できないことを誰かが証明または反証できますか?

ある言語を与えられた場合、それが規則的であるか、CF であるが規則的ではないか、句構造であるが CF ではないかをどのように判断しますか? この問題に対処する良い方法はありますか? ランダムに FA や PDA を作成することもできますが、もっと良い方法があると思います。

古典的な例:

L = { a^nb^nc^n | n >= 0}

どこから始めますか？ありがとう。

私は離散数学における正規言語の定義とその応用 (Rosen)を理解しようとしましたが、この本の定義がそのようなものである理由を理解するという目標に到達することはできませんでした。ページ（789）で、定義を言い換えています：

タイプ 3 文法は次のように定義されます。

w1 は非終端記号で、w2 は次の形式です。

ここで、B は非終端記号で、a は終端記号です。特殊なケースは、w1 が開始記号で、w2 がラムダ (空の文字列) の場合です。

答えが見つからなかった2つの質問。まず、 w2をBaの形式にできないのはなぜですか。第二に、ラムダが開始シンボルのみに許可される理由. この本には、通常の言語は有限状態オートマトンと同等であり、両方のケースで FSA を構築できることが簡単にわかると述べられています。他のリソースを調べましたが、これらのリソースにはこれらの制限はありません。

正規表現だけを使用して、特定の文字列が有効な正規表現であるかどうかを検出することは可能ですか?

有効な正規表現である場合とそうでない場合があるいくつかの文字列があるとします。有効な正規表現に対応する文字列に正規表現を一致させたいと思います。それは可能ですか？それとも、これを検出するために高レベルの文法 (つまり、文脈自由言語) を使用する必要がありますか? Perl 正規表現のような正規表現の拡張バージョンを使用している場合、影響はありますか?

それが可能な場合、正規表現に一致する正規表現は何ですか?

I'm trying to use Ragel to implement a simple yes/no fsm. Unfortunately the language specification consists of the union of about a thousand regular expressions, with * operators appearing once or more in the majority of them. So, the number of possible states explodes and it seems it will be impossible to use Ragel to generate an fsm for my language. Is there a tool out there that can do what I need, or should I swap approaches? I need something better than checking input strings against each regular expression in turn. I could chop up the thousand regular expressions into chunks of ~50 and generate an fsm for each, and run every input string against all the machines, but if there's a tool that can handle this kind of job without such a hack I'd be pleased to hear of it.

Thanks!

初歩的な英語で申し訳ありません。文法上の誤りなどを避けるために最善を尽くします。

2 週間前、私は手で手に入れた数学の教材、特に私が登録しているオートマトン理論と計算のコースの通常言語を実装しながら、Scheme (およびその啓蒙) の知識を新たにすることにしました。

これまでのところ、私はアルファベットを記号のリストとして表現してきました。

1. 可変サイズの文字が必要なため、文字のリスト。
2. 文字列のリストは、エレガントではないと感じるからです。

私は経験が浅いので、この特定の選択についてあなたの意見を知りたいです. シンボルは特定の種類のタスク用に予約されていますか?これにより、シンボルを誤用していますか? これに関するコメントは、ガイダンスを求めているため、非常に高く評価されます。

さらに進むと、無限にあるアルファベットで可能なすべての単語のセットを実装する時が来るでしょう。許可される単語の最大サイズによってセットを制限することを考えていました。繰り返しますが、これは良い習慣ですか、それとも代わりにストリームに行くべきですか? ストリームの方がより良いアプローチだと思いますが、まだ学んでいないので、ストリームを使用することの意味がよくわかりません。

とにかく、提案やコメントは大歓迎です。私の疑問を読むのに時間を割いていただき、本当に感謝しています。良い週末を！

部分文字列として aa と bb の両方を含むか、または含まないアルファベット {a,b} の文字列のセットの FA を指定します。これは、FA が aa と bb を含まないすべての文字列を部分文字列として受け入れることを意味します。間違っている場合は修正して、ヒントを教えてください。皆さんありがとう。:D

RE / NFAとDFAを読んだ後、文字列内の部分文字列の検索は、ブルートフォースO（mn）検索ではなく、REを使用すると実際には漸近的に高速になる可能性があります。私の推論は、DFAが実際に状態を維持し、「干し草の山」内の各文字を複数回処理することを回避するということです。したがって、長い文字列での検索は、正規表現を使用すると実際にははるかに高速になる可能性があります。

もちろん、これはNFAからDFAに変換するREマッチャーにのみ有効です。

ブルートフォースマッチャーではなくREを使用した場合、実際にストリングマッチのパフォーマンスが向上した人はいますか？

ほとんどの言語では、固定長または有限長の後読みが許可されています。注目すべき例外の 1 つは .NET で、* 演算子を使用できます。

ただし、.NET 正規表現は、通常の言語ではない名前付きキャプチャを使用して、バランスの取れた括弧を既に認識できます。後読みで*を使用した正規表現はまだ定期的ですか? * 以外の部分式に対する拡張回答 (たとえば、追加のルックアラウンド!) も歓迎します。

tl;dr: 後読みで * を使用しても、正規表現は正常に機能しますか?