DFAで受け入れられる言語をより洗練された方法で表現できますか？

Question

私は2つのDFAを与えられます。 *は最終状態を示し、 - >はアルファベット{a、b}で定義される初期状態を示す。

1） - > Aの場合はA→Aへ、bの場合は* Bへ行きます。 *付きのBは* Bになります。 * Bは - > Aに行きます。

このため、正規表現は明らかである： EはL1である= {W上{A * Bの（* +（*のBAの*のBA *）*）

そして、それが受け入れる言語= 、b} | wは任意の数のaの前に任意の数のaが続き、任意の数aの前に任意の数のbb​​が続き、bbの途中、末尾または先頭に任意の数のaが続きます。

2） - > * Aとbは - > * A - > * Aとなり、* Bとなります。 Bは - >に行きます。* BはC.に進み、C.はC.に進みます。

注：Aは最終状態と初期状態の両方です。 Bは最終状態です。

今、私はこれを取得する正規表現は次のとおりです。

E =のb *（（AB）* +（* A）* BB）

最後に、このDFAが受け入れる言語は以下のとおりです。 L2 = {w、{a、b} | wはn 1の後にk 01またはaが続き、m 11、r 0はn、km、r> = 0である。

ここで問題となるのは、言語L1およびL2それは醜いように見えるからです。前もって感謝します。

Answer 1

E = a* b(a* + (a* ba* ba*)*) 
    = a*ba* + a*b(a* ba* ba*)* 
    = a*ba* + a*b(a*ba*ba*)*a* 
    = a*b(a*ba*ba*)*a* 
    = a*b(a*ba*b)*a* 

これはaとb Sの奇数を含むbのすべての文字列の言語です。これは、最もコンパクトに記号的に{w in {a,b}* | #b(w) = 1 (mod 2)}と表示されます。 1秒間

：状態Bに到達する唯一の方法は、Aにaを参照することで、外部からCCに到達する唯一の方法は、Bにaを参照することです。 Cはデッドステートで、唯一の方法はAで始まるaaです。つまり、1行に2つの文字が表示されている場合、その文字列は言語に含まれていません。言語はaおよびbを超えるすべての文字列の集合で、部分文字列aaを含んでいません。これは、最もコンパクトに象徴的に{(a+b)*aa(a+b)*}^cと表示されます。ここで、は「補数」を意味します。