オートマトン、チェックストリングは言語で受け入れられる| C++

Question

は、これが私のオートマトンであり、この言語のこと正規表現は、私がチェック入力文字列のためのC++プログラムを作りたい

(aaa*b|ba)a*は、この言語かによって受け入れられています。

このプログラムは、文字列やプリントを得る

AcceptedまたはRejected例えば

：

入力： aaaba - 出力：受け入れ

入力： BAA - 出力：承諾

入力： AAA - 出力：拒否

Answer 1

#include <string> 
#include <iostream> 

bool check_string(const std::string& s) { 
    static constexpr int INV = -1; 
    static constexpr int INITIAL_STATE = 0; 
    static constexpr int ACCEPTING_STATE = 3; 
    static const int transition_table[5][2] = { 
    // a b 
    { 1, 2 }, // 0 
    { 4, INV }, // 1 
    { 3, INV }, // 2 
    { 3, INV }, // 3 
    { 4, 3 } // 4 
    }; 

    int state = INITIAL_STATE; 
    for (char c : s) { 
    if (c != 'a' && c != 'b') return false; 
    state = transition_table[state][c - 'a']; 
    if (state == INV) return false; 
    } 
    return state == ACCEPTING_STATE; 
} 

int main(int argc, char* argv[]) { 
    if (argc != 2) { 
    std::cerr << "Usage: check str\n"; 
    return 1; 
    } 
    if (check_string(argv[1])) 
    std::cout << "Accepted\n"; 
    else 
    std::cout << "Rejected\n"; 
    return 0; 
} 

Answer 2

あなたのDFAは絶対に正しいとあなたは、仕事のほとんどを持っています。残りの仕事を私に許可してください。

文字列を受け入れるか拒否するかによって、文字列を引数として受け取り、trueまたはfalseを返す関数を考えてみましょう。

キーアイデア

主なアイデアは、有限状態マシンの状態を使用して、ステップバイステップの文字列を処理することです。コードは非常にシンプルで簡単に書くことができます。なぜなら、有限状態マシンが異なる状態を横断し、は、オートマトンと同じように異なる状態で入力文字列を処理するからです。

は、我々は状態0で始まり、あなたのオートマトンここ

簡単な説明があるの図に従ってください。

文字列がaで始まる場合、次の状態は1です。文字列がbで始まる場合、次の状態は2であり、文字列がどちらにも始まらない場合、文字列は拒否されます。

現在の状態が1または2で次の文字がaではないにもかかわらず、文字列は拒否されます。

次の文字がaの場合、次の状態は現在の状態に応じて3または4です。

これが処理されると、現在の状態が3の場合、文字列の終わりまではaa ...... aaaとみなす必要があります。また、ある時点で他の文字がある場合は、その文字列は拒否されます。

もし現在の状態が4なら、我々は再びaa ...... aaaを世話しますが、aa ..... aaaの後にbの出現も1つあります。我々はaaの世話をする........ aaa。 **拒否

bool check_string(string str) 
{ 
int state = 0;  

if(str[i] == 'a') 
    { state = 1; ++i; } 

else if(str[i] == 'b') 
    { state = 2; ++i; } 

else return false; 

if(str[i] != 'a') 
    return false; 

else if(state == 1) 
    {state = 4; ++i; } 

else if(state == 2) 
    {state = 3; ++i; } 

if(state == 3) 
{ 
    while(i < str.length()) 
    { 
    if(str[i++] != 'a') 
    return false; 
    } 
    return true; 
} 

if(state == 4) 
{ 
    while(i < str.length()&& str[i++] == 'a') 
    { 

    } 
    if(i == str.length()) 
    return false; 
    else if(str[i] == 'b') 
    { 
    while(i < str.length()) 
    { 
    if(str[i++] != 'a') 
    return false; 
    } 
    return true; 
    } 
    else return false; 
}