정규수식을 입력으로 하여 DFA로 변환하는 프로그램(오토마타)

소개글

정규수식을 입력으로 하여 DFA로 변환하는 프로그램(오토마타)

목차

[[ 문제 설명 ]]
[[ 개략 알고리즘 ]]
[[ 프로그램 소스 ]]
[[ 프로그램 수행결과 및 결과분석 ]]
▷▶ 수행 1 ◀◁
▷▶ 수행 2 ◀◁
▷▶ 수행 3 ◀◁
▷▶ 수행 4 ◀◁
[[ Discussion ]]

본문내용

[[ 문제 설명 ]]
◎ 임의의 정규수식(Regular Expression(이하 정규수식))을 입력으로 하여 DFA로 변환하는 프로그램을 작성하라.
￭ 입력 : 임의의 정규수식
￭ 출력 : DFA의 state table 및 test string의 인식여부
￭ 입력 알파벳은 2개로 하고, state는 임의의 개수를 처리할 수 있도록 프로그램 할 것

[[ 개략 알고리즘 ]]
◎ 먼저 본 프로그램은 자바(J2SDK1.4.1)로 제작되었습니다.
◎ 소스내에 RegNtoD 와 NtoDState 두 개의 클래스가 있습니다. RegNtoD 클래스는 main()을 포함하고 readR_exp()와 readString()을 통해 정규수식, input String을 각각 String 형으로 입력 받으며 getIn_R_exp_arr()와 getIn_String_arr()을 통해 위에서 입력 받은 두 개의 스트링들을 배열로 변환합니다. 이외에 RegNtoD 클래스에는 처음상태(Current State)와 입력심볼에 대한 다음상태(Next State)를 갖는 객체를 선언하는 메소드 mkNtoDState()와 테스트할 입력 스트링들의 각 심볼에 대한 State의 변화를 리턴 시켜주는 findNextState()메소드가 있습니다. 다음, NtoDState 클래스는 private로 선언된 현재상태, 입력심볼, 다음상태를 갖는 객체를 생성하기 위하여 작성하였습니다. 이 클래스에는 객체 생성시 위 세가지를 저장하는 메소드, 조건검사등의 필요에 의해 위 변수에 접근하기 위한 접근 메소드, 현재상태와 입력 심볼을 비교하여 다음상태를 리턴하는 메소드, 이렇게 7개로 이루어져 있습니다. 이상 클래스에 대해 간단히 정리하였습니다.
◎ 우선 프로그램을 실행하면 readR_exp()메소드에 의해 적절한 형태의 정규수식을 입력받습니다. 제가 작성한 프로그램에서는 xy*x형태의 정규수식만을 입력으로 허용합니다.(예)ab*a, 01*0..)
## Type Regular expression :
입력이 완료되면 위에 getIn_R_exp_arr()메소드에 의해 배열형태로 변환됩니다.

참고 자료

없음