범용튜링기계 구현

소개

레포트 점수 만점, 완벽 소스 구현 되어 있습니다.

목차

1. 문제 인식

2. 문제 접근 방법 및 분석

3. 소스코드 및 주석

4. 결과화면

5. 느낀점

본문내용

1. 문제 인식
범용 튜링 기계와 같이 동작하는 프로그램을 만드시오.
①입력은 input.txt로 튜링 기계의 인코딩 뒤에 이 프로그램의 입력이 따라 나온다.
②튜링 기계의 동작은 output.txt 파일에 한 줄씩 테입을 읽었을 때 각 스텝에서 사용되는 전이 함수와 그때 테입의 상태를 표시하여라.

2. 문제 접근 방법 및 분석
튜링기계를 스트링으로 바꾸는 방법
1. Q={q1,q2,∙∙∙∙qn}일때 는 으로 표시한다
2. ∑={0,1}에서 0과 1은 각각 0과 00으로 표시한다.
3. Γ={0,1,#}에서 0,1,#는 각각 0,00,000으로 표시한다.
4. 방향을 나타내는 L,R,S는 각각 0,00,000으로 표시한다.
5. 전이 δ(q,a)=(p,b,d)은 q,a,p,b,d의 부호를 사이에 1을 두고 차례로 나열한다. 즉 δ(,a)=(,1,L)은 10110010으로 표시한다.
6. TM M의 부호는 전이의 부호를 사이에 11을 두고 사전 순서로 나열하고 앞뒤에 111을 붙인 것이다.
7. 초기 상태는 항상 이다.
8. 정지 상태는 전이의 첫째 원소에 나타나지 않는 상태이다. 언어를 결정할 경우 H={y,n}인데 이때 y는 두 정지상태 중 사전 순서가 작은 것이고 n은 큰 것이다.

①while문활용
함수가 몇 개가 될지 모르기 때문에 while문을 활용하여 함수가 몇 개이든 함수가 모두 끝날때까지 입력받을수 있도록 하였습니다. 함수의 시작과 끝은 ‘111’이므로 ‘111’로 시작이 되고 ‘111’이 다시 나올때까지 while문을 반복했습니다.

②함수 분석
우선 함수의 시작인 ‘111’을 찾도록 하고 0의 개수를 파악하여 상태를 알고 1을 경계로 입력상태를 파악하고 1을 경계로 다음 변하는 상태, 그리고 바꿀 데이터, 왼쪽으로 갈지 오른쪽으로 갈지 정지할지 파악까지 0의 숫자로 파악한후 ‘111’이 나올때까지 함수의 입력을 반복했습니다.
0의 숫자를 파악하기 위해서 0의 숫자를 세는 함수를 따로 만들어 호출하였으며 1의 숫자가 연속적으로 2개가 나오면 무조건 에러입니다. 왜냐하면 1은 단지 0의 경계일뿐이지 데이터가 아니기 때문입니다. 그래서 1의 숫자를 하나의 데이터를 받을때마다 검사하여 잘못 입력되었다면 에러메시지를 출력하도록 하였습니다.

참고자료

· 없음