[오토마타] NFA to DFA

등록일 2003.06.04 한글 (hwp) | 7페이지 | 가격 1,000원

목차

1.Question
2.Algorithm
3.Source
4.Result
5.Discuss

본문내용

NFA to DFA

문제
임의의 NFA를 테이블로 입력하여 DFA로 변환하여 출력하는 프로그램 작성하는 것으로 입력 State 개수에는 제한이 없어야 하며 입력 알파벳은 두 개 이상으로 한다.
이를 구현하기 위해서 Reachable Set을 이용해야 하는데 Reachable Set을 프로그램으로 구현하는 것이 이번 과제라 할 수 있다.

개략 알고리즘
NFA는 Char *를 사용하여 Current State 1개와 Next State 2개 가지도록 cNode class 생성
부분집합 형태로 나오는 DFA는 각 집합을 연속적으로 Concatenation 한 후, Sort와 Reduction을 함 임시 저장 공간인 cTable 클래스를 참조하여 중복되는지 여부를 판단. 중복되면 사용하지 않고 중복되지 않는다면 cTable내에 Queue 에 저장 (Queue 안의 내용이 없어질 때까지 반복)

결과분석
실행결과를 0, 1, 2 과 같은 형태를 State로 하여 표현하지 않고, char *table[10]에 참조하여 집합형태로 표현하였다. 이와 같은 결과는 직접 Reachable Set으로 검증해본 결과 정확하다. 하지만 모든 자료를 Char 배열을 이용하여 처리하니, 메모리 소모가 커 Turbo C++ 3.0에서 메모리를 모델을 Huge로 하고 컴파일하여 결과를 출력하였다.
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      최근 본 자료더보기
      추천도서