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

Presentation on theme: "주요 내용 형식 언어와 문법 정규식과 정규 집합 유한 상태 기계 정규 문법과 유한 상태 기계와 정규집합."— Presentation transcript:

1

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

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

4 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

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

6 문법(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’

7 예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

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

9 예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} 이때 단어 은 다음과 같이 유도된다. S  AB0 A010 BB010 

10 예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

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

12 예: 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} 이다.

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

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

15

16 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

17 예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

18 예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

19 예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

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

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

22 예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 

23 예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

24 예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

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

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

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

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

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

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

31 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, ...}

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

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

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

35 예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))*

36 정규 집합(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, …}

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

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

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

40 유한 상태 기계 (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

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

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

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

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

45 출력이 있는 유한 상태 기계: 예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

46 출력이 있는 유한 상태 기계: 예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

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

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

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

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

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

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

53 아래와 같은 유한 상태 오토마타 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이 인식한다.

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

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

56 예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로 된 임의의 문자열}

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

58 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

59 상태 전이 함수 예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}

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

61 상태 전이 함수 예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}

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

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

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

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

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

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

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

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

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

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

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

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