[오토마타] 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로 하고 컴파일하여 결과를 출력하였다.
*원하는 자료를 검색 해 보세요.
  • [컴파일러,형식언어,오토마타]NFA- DFA 5페이지
    : main.cpp 내용 : NFA로 정의된 입력을 받아 축약된 DFA ... 로 바꾸어 출력 컴파일러 / 테스트 환경 : MS VC++ 6.0 ... ("<< NFA입력을 DFA출력으로 변환 >>\n"); printf("-- NFA
  • [컴파일러]NFA-DFA 0페이지
    ][SYMBOLS]; //NFA table int DFA_states ... ]; //DFA table /* NFA table를 출력해준다. q0를 0. q1 ... ] = "01"; NFA_states = 2; DFA_states = 0
  • [컴파일러] 자바로 구현한 dfanfa로 변환하는 프로그램 20페이지
    //자바로 구현한 dfanfa로 변환하는 프로그램 import ... Frame f = new Frame("NFADFA로..."); static ... void convert_NFA_to_DFA() { for(int i=0;i<5
  • NFA to DFA nfadfa로 변환하는 프로그램과 레포트 0페이지
    NFADFA로 변환하는 프로그램으로 레포트랑 같이 있습니다.실행 ... 이렇게 실행하시면 됩니다. 컴파일러입문 혹은 형식언어를 배우시는 분들한테 도움이 될 거에요~ ... 놓은 nfa파일 (소스안에 보면 test.fa)있습니다. 이 두개 파일을
  • 오토마타 DFA C언어 실수의 형식 검증 0페이지
    NFA를 설계하여C언어로실수면 승인실수가 아니면 거부하는 DFA
  • 컴파일러 제 3장 연습문제 14페이지
    부터 pn 중에 하나를 선택할 수 있다는 것이다. ⑧ NFADFA ... 다음 NFADFA로 바꾸시오. ① M = ({q0, q1, q2 ... -NFA M을 고안하시오. ⑵ M을 DFA M'로 바꾸시오. ⑶ M'이
  • 오토마타 유한 상태 인식기 0페이지
    정규 표현식을 입력받으면 e-NFA를 만든 후 최종적으로 minimum DFA로 만든다.
더보기
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      4. 지식포인트 보유 시 지식포인트가 차감되며
         미보유 시 아이디당 1일 3회만 제공됩니다.
      상세하단 배너
      최근 본 자료더보기
      상세우측 배너
      상세우측 배너
      추천도서
      [오토마타] NFA to DFA