이번엔 \(\varepsilon\)-전이가 없는 NFA를 DFA로 변환해보자. 변환 알고리즘은 다음과 같다. NFA에 의해 인식되는 언어를 L이라고 하면 L을 인식하는 DFA가 존재한다. L을 인식하는 NFA \(M = (Q, \sum , \delta , q_0, F\)라 하면 L을 인식하는 DFA \(M^\prime = (Q^\prime, \sum , \delta^\prime, q_0^\prime, F^\prime\)는 다음과 같이 구성된다. \(Q^\prime = 2^Q\), 즉 \(Q^\prime\)의 한 상태는 \([q_1, q_2, \cdots , q_i]\)의 형태로 나타낸다. 단, \(q_j \in Q(j=1, 2, \cdots , i\)이다. \(F^\prime=\{q \in Q^\prim..

NFA에서 DFA로 변환하기 전에 NFA와 DFA가 서로 동등해야만 변환의 의미가 있다. 다만 증명 부분은 생략한다. NFA와 DFA는 동등하다는 것만 알고 넘어가자. \(\varepsilon\)-전이가 있는 NFA를 DFA로 변환 \(\varepsilon\)-closure를 이용하여 변환하는데 NFA에서 의미가 같은 여러 개의 상태가 DFA에서 하나의 상태로 변환되는 것이다. 먼저 \(\varepsilon\)-closure(S)에 대한 정의부터 살펴보자. \(\varepsilon\)-closure(S) S가 하나의 상태일 경우 \(\varepsilon\)-closure(S)는 NFA의 상태 S와 상태 S로부터 \(\varepsilon\)-전이에 의해 도달될 수 있는 NFA의 모든 상태의 결합이다. 이 ..

1. 오토마타란? 디지털 컴퓨터의 추상적 모델로서 입력 자료를 읽는 입력장치, 출력을 하는 출력장치, 무한개의 기억 소자로 이루어진 임시 기억장치, 유한개의 내부 상태 중 하나의 상태를 항상 유지하는 제어장치로 구성된다. 글로 써놓으니 와닿지는 않는데 그냥 컴퓨터를 추상적으로 표현한 것과 같다. 오토마타는 결정적 오토마타와 비결정적 오토마타로 구분할 수 있다. 결정적 오토마타(deterministic automata) 한 상태에서 하나의 입력을 받았을 때 다음 상태가 유일하다. 비결정적 오토마타(non-deterministic automata) 한 상태에서 하나의 입력을 받았을 때 다음 상태가 두 개 이상인 것을 말한다. 지금은 무슨 뜻인지 몰라도 된다. 뒤에서 다시 나오니 이런 것이 있다 정도만 알고 ..

언어: 알파벳으로 생성되는 모든 문자열들의 부분집합이다. 문법: 언어는 문법에 의해서 생성되고 정의된다. 인식기: 언어는 인식기에 의해 인식된다. 문법 언어 인식기 type 0(무제약 문법) 재귀 열거 언어 튜링 기계 type 1(문맥인식 문법) 문맥인식 언어 선형한계 오토마타 type 2(문맥자유 문법) 문맥자유 언어 푸시다운 오토마타 type 3(정규 문법) 정규 언어 유한 오토마타 알파벳 언어의 문장을 이루는 기본적인 기호(Symbol)로 정의한다. 공집합이 아닌 기호들의 유한 집합으로 \( \sum \)로 표시한다. 일반 프로그래밍 언어에서는 사용 가능한 문자나 기호들의 집합이라고 설명한다. C 언어의 경우 영문자, 숫자, 특수 문자 등이 해당된다. 문자열(String) 알파벳 \(\sum\) 에..

1. 컴파일러의 논리적 구조 1. 개요 문장이 어떤 요소로 구성되어 있는지 파악하기 위해 문장에 사용된 단어를 검사한다. I am a boy라는 문장으로 예를 들면 I, am, a, boy 라는 네 가지 단어가 사용된 것을 알 수 있으며 이를 알아내는 것을 어휘 분석이라고 한다. I, am, a, boy 가 각각 8품사인 명사, 대명사, 동사, 형용사, 부사, 전치사, 접속사, 감탄사 중 어디에 속하는지 확인하고 문장의 5대 요소인 주어, 동사, 목적어, 보어, 수식어 등으로 구분할 것이다. 그리고 주어+동사, 주어+동사+보어, 주어+동사+목적어 등 문장의 형식을 검사하여 이 문장이 주어+동사+보어로 구성되었다는 것을 알아낸다. 이렇게 문장의 형식을 알아내는 것을 구문 분석이라고 한다. 단어 대 단어의 ..

1. 컴파일러의 필요성 언어란? 의사전달을 하기 위한 도구 언어의 종류 자연언어 형식언어 프로그래밍 언어 컴파일러가 필요한 이유 인간은 문제를 해결하기 위해 컴퓨터를 사용하며 컴퓨터와 의사소통을 하기 위한 언어가 필요하다. 컴퓨터는 기계어를 사용하지만 인간이 기계어를 사용하여 문제를 표현하기란 무척 어렵기 때문에 인간은 사람 중심 언어인 고급 언어를 사용한다. 그러나 컴퓨터는 인간이 사용하는 고급 언어를 이해하지 못한다. 따라서 인간이 사용하는 고급 언어를 기계어로 변환해주는 번역기인 컴파일러가 필요하다. 2. 프로그래밍 언어 참조 호출과 값 호출 참조 호출 실제 매개변수의 주소를 대응되는 형식 매개변수로 넘겨주는 방법으로 C언어의 포인터 변수에 대한 매개변수 전달 방식에 사용 2개 이상의 변수가 메모리..