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

2-1. 형식언어의 정의 정의 몇 개의 수학적 구조와 함께 기호적 스트링 (Symbolic string)들로 구성 어떤 alphabet에서 Symbol들로 구성되는 string의 집합

정의 2.0 정의 2.1 정의 2.2 Symbol : 언어에 있어서 가장 기본이 되는 요소 예 : 0, 1, ㄱ, A Alphabet : Symbol들의 유한 집합 예 : T1 = {0, 1} , T2 = {ㄱ,ㄴ,·····,ㅎ,ㅏ,ㅑ,····,ㅡ,ㅣ} 정의 2.2 String : Alphabet T에 속하는 Symbol이나 T에 속하는 하나이상의 Symbol 연결 예 : T = {a, b}일 때, a, b, aa, ab, ba, bb, aaa, ····· 는 모두 T에서 만들 수 있는 String이다. (character, 문자) (단어)

String 길이 : String을 이루는 Symbol의 개수 정의 2.3 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 (교환법칙 성립 안 함)  예 : |u| = dog = 3 || = house = 5 u· = u = doghouse |u| = 8

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

T* : empty string을 포함한 T에 속하는 Symbol로 이루어 정의 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 }

정의 2.8 정의 2.9 예 : L = {a, ba, aab} 언어의 곱 (Product) L·L´ = LL´ = {xy | x L, y  L´}  LL´ 예 : L = {a, b} L´ = { ab, bc, cc} LL´ = { a, b} ·{ab, bc, cc} = {aab, abc, acc, bab, bbc, bcc} 정의 2.9 L의 거듭제곱 (Power) 예 : 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} Ln = L·Ln-1

정의 2.10 정의 2.11 언어 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} : 하나의 영문자와 숫자하나와의 조합을 표시 ll : 두개의 영문자 l4 : 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 : terminal Symbol의 유한집합 VN VT =  V(Vocabulary) = VN  VT P : 생성규칙의 유한집합    (유도)  V+   V* S : start Symbol  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방식 Sentence Form Sentence

정의 2.13 예제 1 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 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

sentential form(문장형태) : S =>,  V* 정의 2.14 sentential form(문장형태) : S =>,  V* sentence (문장) :   Vt 문장 형태 중 nonterminal symbol을 포함하지 않은 것 정의 2.15 L(G) = { | S => ,  Vt } 예제 3 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} * * *

주어진 문법으로부터 생성되는 언어를 찾는 과정은 일정한 규칙이 없기 때문에 반복적인 연습이 필요하다.  예제 4 G2 = ({O, E} , {a}, P, O} P : O a O  aE E  O i) O => a ii) O => aE => aaO => aaa iii) O => aE => aaaE => aaaaO => aaaaa L(G2) = {a2n+1 | n 0}  예제 5 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 L1 = {anbn | n 1} i) 같은 수의 terminal symbol을 생성해야 하므로 nonterminal symbol이 terminal symbol사이에 내장되어 있어야 한다. S  aSb (embedded 생성규칙) ii) 최소한의 terminal symbol은 nonterminal symbol을 필요로 하지 않기 때문에 따로 구분 지어 주어야 한다. S  ab  S  aSb | ab

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

2-3. 형식 언어의 문법의 분류 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 3(Regular Grammar : rg : 정규문법) Type 2 (Context-free Grammar:cfg) 왼쪽은 하나의 nonterminal symbol만 가능     : nonterminal  V* 예제 ) L(G2) = {anban | n 1} G2 = ({S, C}, {a, b}, P, S), P : S  aCa C  aCa C  b Type 3(Regular Grammar : rg : 정규문법) 왼쪽에 하나의 nonterminal symbol이 오고, 오른쪽도 최대한 하나의 nonteminal symbol이거나 terminal 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 언어  언어의 포함관계  문법형태에 따른 언어와 인식기