ノン・レギュラーがレギュラーのサブセットではなく、ユニオンがレギュラーである非正規・正規言語がありますか?

$ L1 $、$ L2 $という言語は存在しますか?$ L1 $は通常ではありません。$ L2 $は通常の$ L1 not
subset L2 $と$ L1 cup L2 $は通常ですか?

ベストアンサー

私はタイトルの質問、すなわち$ L_1 not subset L_2 $に行くつもりです。 質問の本文では代わりに$
L_1 subsetneq L_2 $を書いていました。これは、$ L_1 $が$ L_2
$の厳密なサブセットであることを意味します。

$ L_1 $を非正規語にする。 L_1 $の$ x を$ L_1 $の要素にする。次に、$ L_2 = Sigma
setminus {x } $を設定します。

  1. $ L_2 $は、$ x $以外の単語を受け入れる簡単なNFAがあるため、明確に規則的です。
  2. $ L_1 $は定義通りではありません。
  3. $ L_1 setminus L_2 = {x } neq emptyset $したがって$ L_1
    not subset L_2 $
  4. $ L_1 cup L_2 = Sigma $は明らかに普通の言語です。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です