[오토마타] 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로 바꾸어주는 프로그램 9페이지
    #include #include #define STATES99#define SYMBOLS20int N_symbols;/* number of input symbols */int N_NFA_states;/* number of NFA sta..
  • [컴파일러]NFA-DFA 0페이지
    #include #include #define STATES256#define SYMBOLS20int N_symbols;// 입력symbol의 수 int NFA_states;// NFA 상태의 수 char *NFAtab[STATES][S..
  • [컴파일러,형식언어,오토마타]NFA- DFA 5페이지
    #include #include #include "fa.h"void InitFA(FA *fa);// fa구조체값들으 초기화시킴int InputNFA(FA *NFA);// NFA의 값을 각각 입력 받아 FA구조체에 저장void Outpu..
  • [알고리즘] NFA를 축약된 DFA로 바꾸는 프로그램 분석 14페이지
    3.20 NFA를 축약된 DFA로 바꾸는 프로그램을 작성하시오.(C 언어로 구현했습니다.)/* (1) 정규수식 --> ε- NFA (2) ε- NFA --> DFA (3) DFA --> minimized DFA (4) minimized DFA에 의해 입력스트링을..
  • 정규수식 -> NFA -> DFA -> Minimum State DFA 0페이지
    #define Max_char 100// 정규수식의 길이// 데이터 형 선언typedef enum {True = 1, False = 0} Bool;typedef struct state* State;// 스테이스 상태 저장 struct state{int q;//스테이트i..
  • NFA to DFA nfa를 dfa로 변환하는 프로그램과 레포트 0페이지
    NFA를 DFA로 변환하는 프로그램으로 레포트랑 같이 있습니다.실행방법은 컴파일을 하시고요~ 그 실행 파일을 가지고 실행하시면 돼는데요 실행파일은 Debug에서 만들어 지고요~ Debug 안에 nfadfa.exe 실행 파일이 있구요이 실행 파일을 가지고 도스창에서 제..
  • [컴파일러] 컴파일러 3장 20번 문제 14페이지
    3.20 NFA를 축약된 DFA로 바꾸는 프로그램을 작성하시오.(C 언어로 구현했습니다.)/* (1) 정규수식 --> ε- NFA (2) ε- NFA --> DFA (3) DFA --> minimized DFA (4) minimized DFA에 의해 입력스트링을..
더보기
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      최근 본 자료더보기
      추천도서