형식언어와 유한상태기계

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

언어(language) S : 기호들의 집합 S*: S로부터 만들어지는 모든 유한 스트링들 예) S: 알파벳 Ex) S={정수, +, -, x, , (, )} S*: 모든 가능한 수식들(algebraic expressions)

언어의 구성요소 언어: 다음의 세가지 요소로 구성된다. 기호들(알파벳)의 집합 S가 반드시 존재한다. S로부터 문장들의 집합 S*를 형성하는 규칙이 반드시 존재한다. (syntax) (3) 규칙에 합당하게 만들어진 문장들이 어떤 의미를 갖는지를 반드시 결정할 수 있어야 한다. (semantics)

Syntax와 Semantics Ex) “Going to the store John George to sing” Syntax: the specification of the proper construction of sentence Semantics: the specification of the meaning of sentences 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

심벌(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은 이 문법에서 만들어지는가? 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은 이 문법에서 만들어지는가? 이때 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 Abbbbbbc은 이 문법에서 만들어지는가? 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를 생성하는 규칙을 BNF로 표시하라 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로 표시된 생성 규칙을 정규식으로 표현하라. <v0> ::= a<w> <w> ::= bb<w> | c 정규식 a(bb)*c

다음과 같은 문법 다이어그램으로 표시된 생성 규칙을 정규식으로 표현하라. 정규식 a∪b∪c*