【컴파일러구성】인터프리터 및 DFA, NFA 상태전이도

안녕하세요 【키보드 워리어】

 

⌨🗡🧑

블로그 방문자 여러분, 안경닦이입니다.

 

---

 

 

 

컴파일러와 인터프리터의 차이점이 무엇일까?

 

컴파일러는 고급언어로 쓰인 원시 프로그램을 입력으로 받아 컴퓨터에서 직접 실행 가능한 형태의 목적 프로그램을 출력으로 내보내 주는 시스템 소프트웨어로, 고급 프로그래밍 언어를 기계어로 번역하는 프로그램입니다

 

인터프리터는 컴파일러처럼 고급 언어를 기계어로 번역해주는 역할을 수행합니다

 

단, 컴파일러는 원시 코드 전체를 읽은 다음 이를 기계어로 번역해 주는데 비하여

인터프리터는 원시 코드를 한 줄씩 읽어 들여 목적 코드로 바꾸어줍니다

 

컴파일러는 번역 후 실행해주어 효율적이며 반복문 처리에 효과적입니다 인터프리터는 실행시간이 긴 단점이 있지만, 사용자와 대화식으로 진행하여 융통성이 있습니다

 

실행 속도는 컴파일러가 빠르지만, 번역 속도는 인터프리터가 빠릅니다

 

DFA 전이 함수표를 보고 DFA 상태 전이도를 어떻게 그릴까?

 

 

δ	0	1
q0	q1	q0
q1	q2	q0
q2	q2	q0

<DFA 전이함수표 예시>

 

 

<그릴 때 유의사항!>

- Start 부분은 화살표로 구분해주어야 한다

- 델타 표 열에 있는 대로 작성해준다

- 델타표 마지막 열에 있는 항목엔 final 표시해주어야 한다.

 

DFA 상태전이도 그림

 

 

인식 유무는 어떻게 판단할 수 있을까?

1) 101101을 인식하나요?

Start부터 시작하여 q0 > q1 > q0 > q0 > q1 > q0으로 끝나게 되므로 인식 불가함

 

2) 111000을 인식하나요?

Start부터 시작하여 q0 > q0 > q0 > q1 > q2 > q2로 끝나게 되므로 인식함

 

3) 010101을 인식하나요?

Start부터 시작하여 q1 > q0 > q1 > q0 > q1 > q0으로 끝나게 되므로 인식 불가함

 

 

NFA 전이 함수표를  DFA 전이 함수표로 변환해보기

 

δ′	0	1
[q0]	[q1, q2]	[q0]
[q1]	[q2]	∅
[q2]	∅	[q1]
[q1, q2]	[q2]	[q1]

델타 열 항목에 있는 것을 A, B, C, D로 잡아서 똑같이 생긴걸 그대로 입력해주면 돼요, 쉽죠?

δ	0	1
A	D	A
B	C	∅
C	∅	B
D	C	B