[오토마타] 12. Toy Program for DFA

 

위와 같은 언어 L을 DFA로 표현해보자.

주어진 언어는 aa를 포함하는 임의의 a, b로 구성된 문자열을 문장으로 갖는다.

 

 

정규표현식과 DFA 로는 위와 같이 표현할 수 있다.

충분히 어렵지 않다.

 

위 언어는 regular expression 으로 표현할 수 있고, 또는 DFA로 나타낼 수 있었으므로 Regual Language 이다.

 

이제 이 DFA를 파이썬 코드로 작성해보자.

 

 

DFA의 트랜지션 함수는 위와 같다.

 

 

DFA 함수를 위와 같이 정의한다.

s 라는 전체 문장에서 심볼을 하나씩 읽으면서 현재 상태에서 이 심볼을 읽었을 때 그 다음 state를 transition map을 통해 결정한다.

전체 심볼을 다 읽었을 때 최종 state가 final state에 속하면 Accepted 이고, 아니라면 Rejected 로 판별할 수 있다.

 

 

 

위는 dfa 함수의 다양한 문자열을 넣어서 문장 여부를 판별한 테스트 결과이다.