DFA là từ viết tắt của Defministic Finite Automata. Nó là một máy trạng thái hữu hạn chấp nhận hoặc một chuỗi dựa trên bộ chấp nhận của nó.
Ở đây, chúng ta sẽ tạo một DFA chấp nhận một chuỗi bắt đầu và kết thúc bằng a. Đầu vào là từ tập hợp (a, b). Dựa trên điều này, chúng tôi sẽ thiết kế một DFA. Bây giờ, hãy thảo luận về một số trường hợp hợp lệ và không hợp lệ được DFA chấp nhận.
Các chuỗi được DFA chấp nhận:ababba, aabba, aa, a.
Các chuỗi không được DFA chấp nhận:ab, b, aabab.
Ví dụ
Chương trình này kiểm tra một chuỗi bắt đầu và kết thúc bằng a. DFA này sẽ chấp nhận tất cả các chuỗi bắt đầu và kết thúc bằng a. Mã kiểm tra sự bình đẳng của phần tử đầu tiên và cuối cùng và mọi thứ ở giữa đều có thể thực hiện được từ (a, b).
#include <iostream>
#include <string.h>
using namespace std;
int main(){
char str[] = {"ababba"};
int lenght = strlen(str);
if(str[0] == 'a' && str[lenght-1] == 'a'){
printf("Accepted");
else{
printf("Rejected");
return 0;
}
}
} Đầu ra
Accepted