問題タブ [regular-language]

私はこれらの表現について、そしてそれらが不規則であるか規則的であるかについて、2番目の意見を得たいと思います。

{0^n 1^m | n >= m >=0} 通常

{0^n 1^m | n,m >=0}*通常

{0^n 0^n | n>=0}不規則

誰かがこれが本当であることを確認できますか？

私の教科書によると、L1 = A* - L1 の補集合は、L1 が正規言語である限り、正規言語です。
A* には、Context Free 言語、Context Sensitive 言語、Recursively Enumerable 言語も含まれていませんか? A*-L1 にはそれらもすべて含まれますね。では、どうすれば定期的になることができますか？
有限ステート マシンの表現の下で、補語がまだ通常の言語である理由がわかりました。しかし、その背後にある理論を理解することはできません。

また、 A* - L1 = A* 交差補数(L1) . 補数によって定義されるもので補数を定義することは、トートロジーではありませんか? それがどのように有効なのか、私にはよくわかりません。

ありがとう。

したがって、いくつかのテストの結果は次のようになります。

私の答えは：3*(11)*2*

しかし、それはいくつかのテストに失敗します...誰かが私を助けることができますか?

2 番目の演習は次のとおりです。

テスト文字列:

私の解決策は(12*)*

しかし、いくつかのテストに失敗します...助けてください。

{(a^p)(b^q):p,Q は N に属する} は通常の言語であるとどこかで読みました。しかし、私はこれが正しいとは思わない。これは、ポンピング補題を使用して証明できます。私のソリューションが正しいかどうかを確認したいだけです

y を ab とする。したがって、n>=1 の場合、a の前に b がいくつかあるため、x(y^n)z は L に属しません。しかし、表現はこれを許しません。したがって、(a^p)(b^q) は RL ではありません

本を読んでいる間、私はこの疑問を抱きました。

それはそれについて言及しています

L = {s∈（0 + 1）* | n0（s）mod 7 = n1（s）mod5 = 0}は通常ですここで、n0（s）= sの0の数、n1（s）=sの1の数

さらにそれはそれを述べています

L = {s∈（0 + 1）* | d（s）mod 5 = 2およびd（s）mod 7！= 4}は規則的ではありません（文脈自由ではありませんが、再帰的です）。ここで、d（s）= sの10進値（例：d（101）= 5）

なんでそうなの？DFAにsの10進値を格納（記憶）するためのメモリがないためですか？しかし、その場合、どうして第一言語が規則的になるのでしょうか？

私はこのような文字列を持っています：

QLPUBの値を無視するにはどうすればよいですか？実際、この文字列を3000行でチェックしたいのですが、50を無視したいと思います。

たとえば、Java正規表現または％sまたは...でそれを無視する方法はありますか？

Ahoさんの本を読んで正規表現を勉強しています。本書の次の 2 つのステートメントが理解できません。

質問 A:

私の質問は、なぜ+1正規表現の最後に追加されるのですか? 1(0+1)*1十分ではありませんか？

また、以下の点で困っています。

質問 B:

以下のように、1 が 1 つしかない 0 と 1 のみを含む文字列のセット

0*+0*10*どのようにして解決策にたどり着いたのか、順を追って説明していただけますか?

正規表現を使用して検証する必要のあるテキストフィールドがあります。私の要件は次のとおりです。

CCCCNNNNNNまたはCCCCNNNNNNN（テンプレート）

1234ABCDEFGまたは123-ABCDEFG（文字列の例）

ルール：

• 文字列全体は最大25文字です
• 最初の4文字（CCCC）は英数字でなければなりません
• CCCCは正確に4文字で、数字または数字にすることができます
• CCCCは4番目の文字としてダッシュ記号を持つことができます
• NNNNNNNNNNNNは最大21文字で、数字のみです。

たとえばAAAA 1234 A58-、CCCCの有効な文字列です。

これが私の研究ノートです：

• 最初に数値を一致させる必要があります
• +このパターンにX回一致するように指定するcharが必要になります
• その後、8〜9スペースの文字を一致させる必要があります

ここに正規表現パターンに関するすばらしい投稿があります：

数値と正規表現の照合—数字とコンマのみ

私の目標は、このREGEXパターンをWinFormsアプリのテキストボックスマスクに適用することです。

で終わる言語の補語を見つけるのを手伝ってくれませんかabab - (a|b)*abab (over an alphabet {a,b})

補数には、abab で終わらないすべての文字列が含まれている必要があると思います。を補完するために DFA を構築した後、Rij-Algorithm でそれを試みること(a|b)*ababができますが、Automaton と Rij なしでどのように機能するかを理解するのを手伝ってください (Automaton には 5 つの状態があるため)。

わかりました、単語を で終わらせることはできませんabab。末尾の's と's の4 文字は 2 ^{4通りあります。}よし、消さなきゃいけないから組み合わせは15通り。補語が.( と を除いたすべての組み合わせの和集合) であることを意味しますか? でも最初から変わらないの？ababab(a|b)*ababab(a|b)

これを理解してください。

私は、チョムスキーによって設定された4つのレベルの形式文法（無制限、文脈依存、文脈自由、通常）のわかりやすい（つまり、非形式的な）説明を見つけようとしています。

形式文法を勉強してからもう少し経ちましたが、今ではいろいろな定義がわかりづらいです。明確にするために、私はあなたがどこにでもある正式な定義を探していません（例えばこことここ-私は他の誰と同じようにグーグルできます）、あるいは実際にはどんな種類の正式な定義さえも探していません。代わりに、私が見つけたいと思っていたのは、完全性のために明快さを犠牲にしない、クリーンでシンプルな説明でした。