이번엔 \(\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) 한 상태에서 하나의 입력을 받았을 때 다음 상태가 두 개 이상인 것을 말한다. 지금은 무슨 뜻인지 몰라도 된다. 뒤에서 다시 나오니 이런 것이 있다 정도만 알고 ..

대표적인 문법 표현 방법은 정규 표현, 구문 도표, BNF, EBNF가 있다. 1. 정규 표현 정규 표현(regular expression)은 정규 언어를 가장 잘 표현할 수 있는 방법이다. 정규 표현은 다음과 같이 재귀적으로 정의된다. 기본 단계 : 기본을 정의하는 세 가지 규칙이 있다. \(\varnothing\)는 공집합을 나타내는 정규 표현이다. \(\varepsilon \)은 공문자열을 나타내는 정규 표현이다. 터미널 기호인 a는 집합 {a}를 나타내는 정규 표현이다. 귀납 단계 : r과 s가 정규 언어 L(r)과 L(s)를 나타내는 정규 표현이라면 (r) + (s)는 L(r) \(\cup\) L(s)를 나타내는 정규 표현이다. (r) \(\cdot\) (s)는 L(r) \(\cdot\) L(s..

형식 문법은 크게 두 가지 방법으로 정의할 수 있다. 생성 규칙(Production Rule)만으로 표현 항목으로 정의 1. 형식 문법 형식 문법 \(G=(V_N,V_T,P,S)\) 는 다음과 같이 네 가지 항목으로 정의된다. \(V_N\): 논터미널 기호의 유한집합 \(V_T\): 터미널 기호의 유한집합 \(V_N\cap V_T=\varnothing ,V_N\cup V_T=V\) 터미널 기호와 논터미널 기호를 문법 기호(grammer symbol)라 하며 보통 \(V^{vocabulary}\)로 표시한다. \(P\): 생성 규칙의 유한집합 \(\alpha \to \beta, \alpha \in V^+, \beta \in V^*\) \(\alpha\)를 왼쪽 부분(left-hand side), \(\be..

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