주요 내용 형식 언어와 문법 정규식과 정규 집합 유한 상태 기계 정규 문법과 유한 상태 기계와 정규집합

언어(language) S : 기호들의 집합 S*: S로부터 만들어지는 모든 유한 스트링들 예) S: 알파벳 Ex) S={정수, +, -, x, , (, )} S*: 모든 가능한 수식들(algebraic expressions) 언어: 다음의 세가지 요소로 구성된다. 기호들(알파벳)의 집합 S가 반드시 존재한다. S로부터 문장들의 집합 S*를 형성하는 규칙이 반드시 존재한다. (syntax) (3) 규칙에 합당하게 만들어진 문장들이 어떤 의미를 갖는지를 반드시 결정할 수 있어야 한다. (semantics)

Ex) “Going to the store John George to sing” “Noiseless blue sounds sit cross-legged under the mountain top.” Ex) ((3-2) (4x7)) 9 (2-3))+4 4-3-2 )2+(3-)x4 Syntax: the specification of the proper construction of sentence Semantics: the specification of the meaning of sentences

심벌(symbol): 기호 알파벳(alphabet): 기호들의 유한 집합 문자열(string): 알파벳에 포함된 기호들이 나열된 것 단어(혹은 문장): 알파벳의 기호들의 문자열 공 문자열(empty string): 길이가 0인 문자열, 로 표시 (공집합과는 다르다.) V: 알파벳의 집합 V*: V에 속한 기호로 만들 수 있는 모든 문자열의 집합

문법(phase-structure grammar) Phase-structure grammar G=(V,T,S,P) V: 기호(문자열)의 집합 T: 단말 기호(terminal symbol) S: 시작 기호(start symbol, seed) P: 생성 규칙(production rule) (로 표시) If w w’, w is replaced by w’

예1: T={John, Jill, drives, jogs, carelessly, rapidly, frequently} N={sentence, noun, verbphrase, verb, adverb} V = T  N S=“sentence” P: 생성 규칙 <sentence>  <noun> <verbphrase> <noun>  John <noun>  Jill <verbphrase>  <verb><adverb> <verb> drives <verb> jogs <adverb> carelessly <adverb> rapidly <adverb> frequently

“Jill drives frequently.”는 문법적으로 맞는 문장인가? <sentence>  <noun> <verbphrase>  Jill <verb><adverb>  Jill drives frequently derivation tree(parse tree) sentence verbphrase noun adverb Jill verb frequently drives

예2: G=(V,T,S,P) N={S}, T={a,b}, V= T  N, P={S aSb, S ab} 이때 단어 a3b3은 다음과 같이 유도된다. S aSb aaSbb aaabbb 예3: G=(V,T,S,P) N={S, A, B}, T={0,1}, V= T  N P={S AB0, A BB, B 01, A1} 이때 단어 0101010은 다음과 같이 유도된다. S  AB0 A010 BB010 0101010

예4: V={v0, w, a, b, c} N={v0, w} T={a, b, c} V = T  N S= v0 P: 생성 규칙 v0  aw w  bbw w  c derivation tree(parse tree) v0 a w b b w b b w b b w c Syntactically correct sentence abbbbbbc=a(bb)*c

언어와 문법 <정의> L(G): 문법 G의 언어 문법 G를 사용하여 만들어질 수 있는 문장들의 집합

예: G=(V,T,S,P) N={S}, T={a, b, A}, V= T  N, P={S aA, S b, A aa} 생성 S aA와 A aa를 이용하면, aaa를 유도할 수 있고 생성 S b로부터 b를 유도할 수 있다. 따라서 문법 G로부터 유도되는 언어는 L(G)={b, aaa} 이다.

문법의 종류(1) 유형0 문법(비제한 문법) 생성에 아무 제약이 없다. 유형1 문법(문맥 의존 문법: context sensitive grammar) A B에서 B의 길이가 A보다 길거나 같고, 혹은 A   유형2 문법(문맥 자유 문법: context free grammar) A B에서 A는 비단말 기호(nonterminal symbol)이고 B는 하나 이상의 기호로 이루어져야 한다.

문법의 종류(2) 유형3 문법(정규 문법: regular grammar) A, B가 비단말 기호이고 a가 단말 기호일 때, A aB 혹은 A a 혹은 A  

G=(V,T,S,P), N={A, B}, T={a, b} 예: (유형1) v0  aAB AB bB B b A  aB 예: (유형2) v0  aBa B  aBa B  b 예: (유형3) v0  aB B bA, B  b, A  aB, A  a

예1: 유형3(정규) 문법 언어 {ambn|m,n>0}을 생성하는 문법 (1) G1=(V,T,S,P) V={S}, T={a,b}, P={S aS, S  Sb, S  } ={S aS|bS|} S aS aaS aaaS aaaSb aaaSbb aaabb (2) G2=(V,T,S,P) V={S, A}, T={a,b}, P={S aS, S  bA, S b, A  bA, A  b, S  } S aS aaS aaaS aaabA aaabb

예2: 유형2 문법(context free) 언어 {anbn|m,n>0}을 생성하는 문법 G=(V,T,S,P) V={S}, T={a,b}, P={S aSb, S  } ={S aSb|} S aSb aaSbb aabb

예3: 유형1 문법(context sensitive) 언어 {anbncn|n>0}을 생성하는 문법 G1=(V,T,S,P) V={S, A, B}, T={a,b,c}, P={S aSAB, BA  AB, aA ab, bA  bb, bB  bc, cB cc, S  } S aSAB aaSABAB aaABAB aabABB aabbBB aabbcB aabbcc

문법의 표현 BNF(Backus-Naur Form) 형식 문법 다이어그램(syntax diagram) 유도 트리(derivation tree)

Backus-Naur Form(BNF) (2) 생성 은 ::=로 표시한다. (3) 하나의 비단말 기호로부터 생성되는 여러 개의 문자열은 |으로 구분한다. P: 생성 규칙 v0  aw w  bbw w  c P: 생성 규칙(BNF 표기법) <v0> ::= a<w> <w> ::= bb<w>|c

예1: C언어에서 사용되는 signed integer을 표기하기 위한 생성 규칙을 BNF로 표시하면. <signed integer> ::= <sign><integer> <sign> ::= +|- <integer> ::= <digit>|<digit><integer> <digit> ::= 0|1|2|3|4|5|6|7|8|9 

예2: 앞에 예제에서 나왔던 문법을 BNF로 표시하면, P: 생성 규칙 <sentence><noun><verbphrase> <noun>  John <noun>  Jill <verbphrase>  <verb><adverb> <verb> drives <verb> jogs <adverb> carelessly <adverb> rapidly <adverb> frequently P: 생성 규칙(BNF 표기) <sentence> ::= <noun><verbphrase> <noun> ::= John|Jill <verbphrase> ::= <verb><adverb> <verb> ::= drives|jogs <adverb>carelessly|rapidly |frequently

예3: Linux에서의 identifier T={a,b,c,…,z,, 0,1,2,..,9} N={identifier, remaining, digit, letter} S=identifier P: <identifier> ::= <letter>| <letter><remaining> <remaining> ::= <letter>|<digit>|<letter><remaining> |<digit><remaining> <letter> ::= a|b|c|…|z|  <digit> ::= 0|1|2|…|8|9 identifier hw1.c remaining letter remaining letter h remaining w digit remaining letter 1  letter c

문법 다이어그램 (syntax diagram) (1) 비단말 기호는 사각형으로, 단말 기호는 원으로 그린다. (2) 생성 과정은 화살표로서 표시한다. (3) 하나의 비단말 기호로부터 생성되는 여러 개의 문자열은 병렬로 놓고 화살표로 표시한다.

예1: 다음의 BNF 표기에 의한 생성 규칙은 문법 다이어그램으로 다음과 같이 표시할 수 있다. <w> ::= <w1><w2><w3>

예2: 다음의 BNF 표기에 의한 생성 규칙은 문법 다이어그램으로 다음과 같이 표시할 수 있다. <w> ::= <w1><w2> | <w1>a | bc<w2>

예3: 다음의 BNF 표기에 의한 생성 규칙은 문법 다이어그램으로 다음과 같이 표시할 수 있다. <w> ::= ab | ab<w>

주요 내용 형식 언어와 문법 정규식과 정규 집합 유한 상태 기계 정규 문법과 유한 상태 기계와 정규집합

정규식(regular expression) 정규 문법은 정규식으로 표현될 수 있으며 정규 문법에 의해서 생성되는 언어는 정규식에 의해서 만들어지는 정규 집합과 동일하다.  * 기호들의 집합 (알파벳) 문자열의 집합 (정규 집합) 정규 문법 (정규식)

I : 기호(symbol)들의 집합(알파벳) I*: 집합 I의 기호들을 결합하여 만들어지는 유한 크기를 갖는 모든 문자열의 집합  ; 공 문자열(empty string) αβ : 문자열 α와 문자열 β의 연결(concatenation) α∪β : 두 문자열 α, β의 합집합 (∪는 +로도 표시한다.) (α)* : 문자열 α가 유한 개수만큼 반복되어 만들어지는 문자열            ∈(α)*, (α)*≡α* 예: a* = {, a, aa, aaa, aaaa, ...} a(b∪c) 혹은 a(b+c) = {ab, ac} ab(bc)* = {ab, abbc, abbcbc, abbcbcbc, ...}

정규식의 정의 I: a set of alphabets I에서 정의되는 정규식은 다음과 같이 재귀적으로 정의된다. 공문자열 는 정규식이다. αI라면 α는 정규식이다. α과 β가 각각 정규식이면 αβ도 정규식이다. α과 β가 각각 정규식이면 α  β 도 정규식이다. α가 정규식이면 α*도 정규식이다.

예1: I={a, b, c} 다음의 정규식은 (1) a* = {, a, aa, aaa, aaaa, …} (2) a(b+c) = {ab, ac} (3) ab(bc)* = {ab, abbc, abbcbc, …}

예2: I={0, 1} 다음의 정규식은 (1) 0*(0+1)* : 0과 1로 이루어진 모든 스트링 (2) 00*(0+1)*1: 0으로 시작해서 1로 끝나는 모든 스트링 (3) (01)*(01+1*)

예3: 101로 끝나는 단어들로 이루어진 언어 (0+1)*101 예4: 0 혹은 1로 이루어져 있고 1은 0이 나온 후에 나타나야 하는 언어 0* 1* 예5: 최소한 세 개의 연속적인 1을 갖는 단어들 (0+1)* 111(0+1)* 예6: 길이가 3의 배수인 문자열 ((0+1) (0+1)(0+1))*

정규 집합(regular set) I: a finite set of symbols I*: 정규 집합(regular set) 정규식으로 나타내지는 모든 문자열을 정규 집합이라고 한다. 예: I={a, b, c}, 그러면 I*=? 다음의 정규식으로 만들어지는 정규집합: a* I* ={, a, aa, aaa, aaaa, …} a(b+c) I* = {ab, ac} ab(bc)* I* = {ab, abbcbc, …}

다음과 같이 BNF로 표시된 생성 규칙은 정규식 a(bb)*c와 동일하다. <v0> ::= a<w> <w> ::= bb<w> | c 다음과 같은 문법 다이어그램으로 표시된 생성 규칙은 정규식 a∪b∪c*와 동일하다.

주요 내용 형식 언어와 문법 정규식과 정규 집합 유한 상태 기계 정규 문법과 유한 상태 기계와 정규집합

유한 상태 기계의 예 T: flip-flop 1 1 1 input 0 1 0 0 1 1 1 0 현재 상태

유한 상태 기계 (finite state machine) 유한 상태 기계 (S, I, f) S: 상태의 집합(a set of states) I: 입력값의 집합(a set of inputs) f: 상태 추이 함수(state transition function) 예: Flip-flop에서 S = {0, 1} I = {0, 1} f(현재상태, 입력값)=결과 상태 f(0,0) = 0, f(1,0)=1, f(0,1)=1, f(1,1)=0

출력이 있는 유한상태 기계 자동 판매기를 모델링한다고 하자. 입력은 100원, 500원 동전을 입력하고 700원이 되었을 때 C와 S 버튼을 입력하면 콜라와 사이다가 나온다. 초과되는 금액은 반납한다.

자동 판매기의 모델링(1) 입력: (100, 500, C, S) 상태: (S0, S1, S2, S3, S4, S5, S6, S7) 출력: (n, 100, 200, 300, 400, 500, 콜라, 사이다)

자동 판매기의 모델링(2) 다음 상태 출력 입력 상태 100 500 C S S0 S1 S5 n S2 S6 S3 S7 S4 200 300 400

정의: 출력이 있는 유한 상태 기계 출력이 있는 유한 상태 기계 (S, I, O, f, g, s0) S: 상태의 집합(a set of states) I: 유한의 입력 알파벳의 집합(a set of inputs) O: 유한의 출력 알파벳 f: 상태 추이 함수(state transition function) g; 출력 함수 s0: 초기 상태

출력이 있는 유한 상태 기계: 예1 S={s0, s1, s2, s3}, I={0,1}, O={0,1} 추이 함수 f와 출력 함수 g 상태 테이블 상태 도표 0,1 s1 1,0 상태 f g input Input 1 s0 s1 s3 s2 1,0 1,1 0,1 s0 s3 start 0,0 0,0 s2 1,1

출력이 있는 유한 상태 기계: 예2 S={s0, s1, s2, s3, s4}, I={0,1}, O={0,1} 추이 함수 f와 출력 함수 g 상태 f g input Input 1 s0 s1 s3 s2 s4

예2: 유한 상태 기계의 상태도표는?

출력이 없는 유한 상태 기계 유한 상태 오토마타(finite state automata)라고도 한다. 유한 상태 기계의 또 다른 형태로서 이 유형의 기계는 출력은 없고 최종 상태의 집합이 존재한다. 따라서 시작 상태에서 최종 상태에 도달하게 하는 입력값들만 이 기계는 인식하게 된다. 이러한 유형의 기계는 언어를 인식하는 기계를 모델링할 때 사용된다.

정의: 유한 상태 오토마타 유한 상태 오토마타 M=(S, I, f, s0, F) S: 유한한 상태 집합 s0:초기 상태(starting states) F: 최종 상태(acceptance states)의 집합

예1 M={S, I, f, s0, F},S={s0, s1, s2}, I={0,1}, F= {s2} f input 상태 0 1 s0 s0 s1 s1 s2 s2 s2 s1 s0 1 s0 s1 s2 1 0,1

예2 M={S, I, f, s0, F} S={s0, s1, s2, s3}, I={0,1}, F= {s0, s2} f input 상태 0 1 s0 s0 s1 s1 s0 s2 s2 s0 s0 s3 s2 s1 상태 도표는?

유한 상태 오토마타 M과 언어 L(M) I* 에 속하는 문자열 W 이 연속적으로 입력될 때 시작 상태 S0 에서 최종상 F로 이동하면, 문자열 W 는 기계 M=(S, I ,f, s0, F) 이 인식 또는 승인한다고 말한다. 기계 M 에 의해서 인식 (또는 승인) 되는 문자열의 집합을 M 에 의해서 인식되는 언어 L(M) 라고 한다. 

아래와 같은 유한 상태 오토마타 M에서 문자열 W=x1x2x3…xn  I* fw: 유한 상태 오토마타에 “x1x2x3…xn”을 입력했을 때 갖는 상태 1 s0 s1 s2 1 0,1 W=01011 fw(S0)=S1 : 문자열 W는 M이 인식하지 못한다. W’=010110 fw’(S0)=S2 : 문자열 W는 M이 인식한다.

예1: 다음의 유한 상태 오토마타 M1에 의해 인식되는 언어 L(M1)을 구하라. M1 의 최종 상태는 S0 가 유일하다. 따라서 L(M1) 을 구하기 위해서는 S0 에서 S0 로 가는 문자열을 구하면 된다. 그것은 하나 이상의 1로 구성되는 문자열이다. 즉 L(M1) = {1n | n =0, 1, ...}

예2: 유한 상태 오토마타 M2에 의해 인식되는 언어 L(M2)을 구하라. M1 의 최종 상태는 S2 가 유일하다. S0 에서 S2 로 가는 문자열은 1과 01이다. 즉 L(M2) = {1, 01}

예3: 유한 상태 오토마타 M3에 의해 인식되는 언어 L(M3)을 구하라. M3 에서 최종 상태는 S0 와 S3 이다. 먼저 S0 에서 S0 로 가는 문자열은 {0n | n =0, 1, ... }이다. S0 에서 S3 로 가는 문자열은 0개 이상의 0이 나온 후 10이 나오고 그 다음에는 0또는 1이 임의의 개수만큼 나오는 것이다. L(M3) = {0n, 0n10X | n =0, 1, ..., and X는 0과 1로 된 임의의 문자열}

L(M)과 L(G) 유한상태 오토마타 M 에 의해서 인식(또는 승인)되는 언어 L(M) 은 언어 L(M) 은 이에 대응하는 정규 문법(regular grammar) 을 만들 수 있다. 따라서 M에 대응하는 정규 문법(regular grammar) 을 G라고 하면 정규 문법 G에 의해서 생성되는 언어와 M에서 인식되는 문자열의 집합은 동일하다. L(M)  L(G) 

M에서 G 만들기 유한상태 오토마타 M이 주어졌을 때 이에 대응하는 정규 문법 G를 만드는 방법은 다음과 같다. M=(S, I, f, s0, F) G=(V, T, S, P) S N(nonterminal symbol) I T(terminal symbol) V = N  T P: 생성 규칙 Si, Sj ∈ S, x ∈ I일 때    만약 f(Si, w) = Sj 이면, Si  wSj    만약 f(Si, w) ∈ F이면, Si  w

상태 전이 함수 예1: M: finite state automata I={a,b}, S={S0, S1, S2} fa(S0)=S0, fb(S0)=S1, fa(S1)=S1 fb(S1)=S2 fa(S2)=S2 fb(S2)=S2 a, b a a s0 s1 s2 b b L(M) L(G) 생성 규칙 S0 aS0 S0 bS1 S1 aS1 S1 bS2 S2 aS2 S2 bS2 S1 b S2 a S2 b G: regular grammar T={a,b}, N={S0, S1, S2}

예1의 L(M)과 L(G)를 regular expression으로 표현하면, a*ba*b(a+b)*

상태 전이 함수 예2: M: finite state automata I={0,1}, S={S0, S1} f0(S0)=S0, f1(S0)=S1, f0(S1)=S1 f1(S1)=S0 1 s0 s1 1 L(M) L(G) 생성 규칙 S0 0S0 S0 1S1 S1 0S1 S1 1S0 S0 1 S1 0 G: regular grammar T={0,1}, N={S0, S1}

예2의 L(M)과 L(G)를 regular expression으로 표현하면, 0은 영향을 주지않는다. 1은 홀수번 나와야 한다. 따라서 0*10*(10*10*)*

주어진 문제를 해결하는 유한상태 오토마타 만들기 주어진 문제를 해결하는 유한상태 오토마타 만들기 a Task Moor machine 일반 언어로 기술 혹은 정규식으로 기술 BNF로 기술

예1: 0과 1로 이루어진 입력 문자열 001을 인식하는 유한상태 오토마타를 설계하라. 즉, I={0,1}, L(M)={001} 1 S0 S1 S2 S3 1 1 0,1 1 S4 0,1

01 혹은 10을 포함하는 문자열만을 인식하는 유한상태 오토마타를 설계하라. 예2: 0과 1로 이루어진 입력 문자열로 문자열 안에 01 혹은 10을 포함하는 문자열만을 인식하는 유한상태 오토마타를 설계하라. 0,1 1 S1 S2 S0 1 S3 S4 1 0,1

예3: x와 y로 이루어진 입력 문자열로 yy로 끝나는 문자열만을 인식하는 유한 상태 오토마타를 설계하라. 문자열만을 인식하는 유한 상태 오토마타를 설계하라. y x y y S0 S1 S2 x x

예4: x와 y로 이루어진 입력 문자열로 x를 포함하지 않는 문자열만을 인식하는 유한 상태 오토마타를 설계하라.

예5: x와 y로 이루어진 입력 문자열로 홀수개의 x를 포함하는 문자열만을 인식하는 유한 상태 오토마타를 설계하라.

문제: 다음의 언어는 정규 언어인가? L = {xnyn | n = 1,2,3,…} 정규식으로 L을 표현할 수 있을까? No. 따라서 위의 언어를 인식하는 유한상태 오토마타를 만들 수 없다. 위의 언어를 인식하기 위해서 튜링 기계(Turing machine)라고 하는 보다 강력한 기계를 사용할 수 있다.

유한상태 오토마타의 최적화 이와 같이 특정 과제를 수행하는 유한상태 오토마타를 설계할 수 있다. 하지만 이와 같이 설계된 유한상태 오토마타는 최적의 기계는 아니다. 즉, 더 적은 상태의 수를 갖는 유한상태 오토마타를 설계할 수 있다. 따라서 다음 단계에서 필요한 것은 최적화된 유한상태 오토마타의 설계이다.

주요 내용 형식 언어와 문법 유한 상태 기계 정규식과 정규 집합 정규 문법과 유한 상태 기계와 정규집합

L(G)와 L(M)과 정규식 G: 정규 문법 L(G)는 정규식으로 표현할 수 있다. M: 유한상태 오토마타

결론 G={V, I, S0, P}: 정규 문법 L(G): 정규 집합 M={S, I, f, S0, F}: 유한 상태 오토마타 L(M): 정규 집합