2. 형식언어 (Formal Language) 2-1. 형식 언어의 정의 2-2. 형식 언어의 문법 (Formal Grammar) 2-3. 형식 언어의 문법의 분류

2-1. 형식언어의 정의 언어(language) : “ 특별한 사회, 국민 또는 민족에 의해 사용되는 단어들의 모임, 그리고 그들을 결합시키는 방법의 모임” 형식언어( formal language) : 일상 생활의 언어와는 달리 기호(symbol)들을 인위적으로 결합시켜 만든 것  잘 정의된 언어(well-defined Language) 형식언어의 정의 : 몇 개의 수학적 구조와 함께 기호적 스트링(Symbolic string)들로 구성 computer 언어와 compiler 설계에 응용됨 Automata 이론과 관련 P. L.은 형식언어의 한 예

Alphabet T : Symbol들의 유한 집합 정의 2.0 Symbol : 언어에 있어서 가장 기본이 되는 요소(character, 문자), 더 이상 세분화될 수 없는 것 (예) 0, 1, ㄱ, A, a, +, , ····· 정의 2.1 Alphabet T : Symbol들의 유한 집합 (예) T1 = {0, 1} , T2 = {ㄱ,ㄴ,·····,ㅎ,ㅏ,ㅑ,····,ㅡ,ㅣ} T3 = {a,b, c,····· z}, T4 = {auto,break, case,····· while} 정의 2.2 String : Alphabet T에 속하는 Symbol이나 T에 속하는 하나 이상의 Symbol 연결 (예) T = {a, b}일 때 a, b, aa, ab, ba, bb, aaa, ·····

정의 2.3 정의 2.4 String의 길이 : String을 이루는 Symbol의 개수 (예)  = 0110 || = 4 u = dog |u| = 3  = house || = 5 정의 2.4 String 접속(Concatenation) : String을 연속으로 연결 해 놓은 것 u = a1····· an,  = b1·····bn 일 때 u· = a1·····anb1·····bn, |u| = |u| + || = n + m u   u (교환법칙 성립 안 함) (예) u = dog, |u | = 3,  = house, | | = 5 u· = u = doghouse |u | = 8

정의 2.5 empty string : 길이가 0인 string , 문자열이 없는 것 (epsilon), (lambda), (null)로 표현 || = || =|| = 0 (예) u = u = u , u = u, dog··house = doghouse an : a가 n개 연결된 string을 표시 (예) a5 = aaaaa a0 : empty String R : String의 역순 (예)  = abc R = cba  = 12····n R = n···· 21

정의 2.6 T* : empty string을 포함한 T에 속하는 Symbol로 이루어질 수 있는 모든 string의 집합 (예) T = {0, 1} T* = {, 0, 1, 00, 01, 10, 11, 000, ···} T+ : T* - {} (예) T = {a, b} T+ = {a, b, aa, ab, ba, bb, aaa, aab, ··· } 정의 2.7 Alphabet T에 대하여 언어 L은 T*의 부분집합이다. (예) T = {a, b} L1 = T* = {, a, b, ab, ba, ···} L2 = { a, ba, aba} L3 = {ap | p는 소수(prime number)} L4 = {anbn | n 1 } <P44 예제 2.5>

(예) L = {a, ba, aab} 정의 2.8 : 두 언어 L과 L´의 곱 (Product) : L·L´ L·L´ = LL´ = {xy | x L, y  L´}  L´L (예) L = {a, b} , L´ = { ab, bc, cc} LL´ = {a,b}·{ab, bc, cc} = {aab, abc, acc, bab, bbc, bcc} <P44 예제 2.6> 정의 2.9 : 언어 L의 거듭 제곱(Power)은 순환적으로 정의 L0 = {}, Ln = L·Ln-1 for n  1 (예) L = {a, ba, aab} L0 = {} L1 = {a, ba, aab} L2 = L·L = {a, ba, aab}·{a, ba, aab} = {aa, aba, aaab, baa, baba, baaab, aaba, aabba, aabaab}

언어 L의 L* (reflexive transitive closure) 정의 2.10 : 언어 L의 L* (reflexive transitive closure) L* = L0L1L2·····Ln···· = Li 정의 2.11 : 언어 L의 L+ (transitive closure) L+ = L1L2L3·····Ln···· = L*  L0 (예) l = {A,·····,Z} , d = {0,····,9} ld = {A,·····,Z}·{0,····,9} = {A0, A1, ·····, A9, B0, B1, ···· B9, C0, ····, Z0, ···· ,Z9} : 하나의 영문자와 숫자 하나와의 조합을 표시 l l : 두 개의 영문자 l 4 : 4자리의 영문자  L*는 엘 스타(L star)로, L+는 엘 대거(L dagger)로 읽는다 i=0

2-2. 형식언어의 문법(Formal Grammar) 정의 2.12 G = ( VN, VT, P, S ) VN : non-terminal Symbol의 유한집합 VT : teminal Symbol의 유한집합 VN VT =  V(Vocabulary) = VN  VT P : 생성규칙의 유한집합    (유도)  V+   V* S : start Symbol S  VN

예제 VN = {<sentence>,<subject>,<verb>,<object>,<noun><article>} VT = {The, Boy, Girl, Loves, .} S = <sentence> P : 1. <sentence>  <subject><verb><object>. 2. <subject>  <article><noun> 3. <object>  <article><noun> 4. <verb>  Loves 5. <article>  The 6. <noun>  Boy | Girl derivation(replacement:유도) <sentence> => <subject><verb><object>. => <article><noun><verb><object>. => The <noun><verb><object>. => The Boy <verb><object>. => The Boy Loves <object>. => The Boy Loves <article><noun>. => The Boy Loves The <noun>. => The Boy Loves The Girl. Left most derivation Top-down방식 Right most derivation Bottom-up방식 Sentential Form Sentence

정의 2.13  derivation(유도) : 한 String에서 생성규칙을 한 번 적용해서 다른 Sting으로 바뀌어진다.  : 한번이상 유도  : 0번 이상 유도 < 예제 1> G = ({S, A},{a, b}, P, S) P : S  aAS S a A SbA A ba A SS i) S => a ii) S => aAS => abaa < 예제 2> (P48 예제 2.9) P : S  aA | bB | A  bS B aS i) S => aA => abS => ab + * ii) S => bB => baS => ba iii) S => aA => abS => abbB => abbaS => abba

정의 2.14 정의 2.15 L(G) : 문법 G에 의해 생성되는 언어 * sentential form(문장형태) : S => ,  V* sentence (문장) :   VT 문장형태 중 nonterminal symbol을 포함하지 않은 것 정의 2.15 L(G) : 문법 G에 의해 생성되는 언어 L(G) = { | S  ,  VT }  <예제 3 > (P48 예제 2.11) G1 = ({S}, {a}, P, S) P : S a | aS i) S => a ii) S => aS => aa iii) S => aS => aaS => aaa L(G1) = { an | n 1} : L(G) 는 시작 심벌로부터 유도될 수 있는 모든 문장의 집합 * * * *

주어진 문법으로부터 생성되는 언어를 찾는 과정은 일정한 규칙이 없기 때문에 반복적인 연습이 필요하다. <예제 4> (P50 예제 2.12) G2 = ({O, E} , {a}, P, O) P : O a O  aE E  aO i) O => a ii) O => aE => aaO => aaa iii) O => aE => aaaE => aaaaO => aaaaa L(G2) = {a2n+1 | n 0} < 예제 5> (P51 예제 2.13) G3 = ({A, B, C}, {a, b, c}, P, A) P : A abc A  aBbc Bb  bB Bc  Cbcc bC  Cb aC  aaB aC  aa i) A => abc ii) A => aBbc => abBc => abCbcc => aCbbcc => aabbcc L(G3) = {anbncn | n 1} 주어진 문법으로부터 생성되는 언어를 찾는 과정은 일정한 규칙이 없기 때문에 반복적인 연습이 필요하다.

문법 작성 : 특정한 형태의 언어를 생성하는 문법을 만드는 일 <예제 1> (P53 예제 2.14) L1 = {anbn | n 1}을 생성하는 문법 i) 같은 수의 terminal symbol을 생성해야 하므로 nonterminal symbol이 terminal symbol사이에 내장되어 있어야 한다. S  aSb (embedded 생성규칙) ii) 최소한의 terminal symbol은 nonterminalsymbol을 필요로 하지 않기 때문에 따로 구분지어 주어야 한다. S  ab  S  aSb | ab

< 예제 2> (P53 예제 2.15) L2 = {0i1j | ij, i, j  1} 1) i > j 일 때, 0이 많은 경우 같은 수의 0과 1을 생성하고 남은 0을 생성을 하면 된다. S  0A1 A  0A1 | 0A | 0 2) i < j 일 때, 1이 많은 경우 같은 수의 0과 1을 생성하고 남은 1을 생성을 하면 된다. S  0B1 B  0B1 | B1 | 1   S  0A1 | 0B1 주어진 문법으로부터 생성되는 언어는 유일하지만, 주어진 언어를 생성하는 문법은 다양한 형태가 될 수 있다.

2-3. 형식 언어의 문법의 분류(p57) Chomsky 4 type Grammar : 생성 규칙의 형태에 따라 구분 Type 0(Unrestricted Grammar) 생성 규칙에 어떤 제한도 두지 않는다. < 예제 > bc  b Type 1(Context-sensitive Grammar :csg) 모든 생성규칙    에서 의 길이가 의 길이보다 길다 . 즉, ||  || <예제> P : A  abc A  aABc Bb  BC CB  cc bc  c (X)

Type 2 (Context-free Grammar:cfg) A : 하나의 nonterminal symbol만 가능,   V* < 예제> L(G2) = {anban | n 1} G2 = ({S, C}, {a, b}, P, S), P : S  aCa C  aCa C  b <P58 예제 2.17 ~ P60 예제 2.18 참조>

Type 3(Regular Grammar : rg : 정규문법) 왼쪽에 하나의 nonterminal symbol이 오고, 오른쪽도 최대한 하나의 nonteminal symbol이거나 teminal symbol로 구성 A  tB A  t t  VT* A,B  VN (right linear regular grammar) A  Bt A  t t  VT* A,B  VN (left linear regular grammar) <예제> L(G3) = {anbam | n, m 1} G3 =({S,B,C}, {a,b}, P, S), P : S  aS S  aB B  bC C  aC C  a

 언어의 포함관계  문법형태에 따른 언어와 인식기 정규언어 Context-free 언어 Context-sensitive 언어 Unrestricted 언어  언어의 포함관계  문법형태에 따른 언어와 인식기