제 6 장. implifictio of Cotet-Free rmmrs d Norml Forms 학습목표 CF 의변환을통한단순화및정규화이해 단순변환테크닉의연마필요
개요 Productio 의우측에허용된자유를약간희생하여큰효과를보자는얘기! * 문법을변환하는방법들 - Useful substitutio rule - Removig λ-productios / uit-productios / useless productios * 정규형식 - Chomsky orml form : 우측항의변수의수제한 - reibch orml form : 우측항의변수와 termil 의위치제한 * CF 를위한간단한 Prsig 방법 : CYK lgorithm - membership lgorithm : 주어진 strig 이문법에맞는지? λ - free lguge L : CFL L λ} ˆ ˆ T T ˆ Pˆ P ˆ Pˆ P 0 0 } ˆ λ} 0 L-λ} 로얻어진결론이쉽게 L 로적용될수있다!
Methods for Trsformig rmmrs Useful ubstitutio Rule ˆ dd delete ˆ ith ˆ ˆ ith : Thm 6. L L y y y P P T y y y P CF P T L L 간단하지만한번증명해볼까요? simplifictio removl of certi types of udesirble productios 수의감소와는무관!
ubstitutio Rule : 증명 ˆ pplied is productio the times of o o. by iductio : ˆ : this ivolves * ivolve ot does this such tht. imilrly ˆ * ˆ ˆ * * ˆ * * L L u y u u u u y u u u u u ii i L pf j j 무지간단하죠! 그럼예를한번들어봅시다.
ubstitutio Rule : 예 예 bc bb b bbbc bbc bb b bbc or bc bbc bbc? useless productios 이런건그냥없애버려도되겠죠?
Methods for Trsformig rmmrs Removig Useless Productios 어떤 derivtio 에도공헌하지못하는 productio 의제거 정의 6. T P : CF : useful iff t lest oe L such tht cf useless * y * ith y T * 예 b λ Q o termil strig λ b Q ot reched from strt symbol
Useless Productios : 예 조금복잡한경우에는그래프를그려보자! e C C Cb i vribles tht c led to but ot C termil strig ii vribles tht cot be reched from strt cf depedecy grph C D iff C Dy ˆ ˆ Tˆ Pˆ ith ˆ } Tˆ Pˆ } 그냥넘어갈순없으니간단히증명
Useless Productios : 증명 Thm 6. T P : CF ˆ ˆ Tˆ Pˆ ithout y useless vribles / productios pf i ˆ 3 : T P repet util o more vribles dded to P P φ dd to such tht such tht symbols re i T } such tht P hs productio L ith * i T * T ii ˆ : dr vrible depedecy grph for fid ll vribles tht cot be reched from remove the vribles / productios
Methods for Trsformig rmmrs 3 Removig λ-productios 정의 6. λ : λ productio * such tht λ : ullble 예 b b L b } o λ λ b b b b 또 증명을해놔야안심!
λ-productios : 증명 Thm 6.3 : CF ith λ ot i equivlet ˆ hvig L o λ - productios pf ll ullble vribles λ put ito repet util o further vribles re dded to N L here L i put ito put to Pˆ L m m N T i N P s ell s ll those by replcig ullble vribles ith λ i ll possible combitios N N 조금복잡한예를가지고작동과정을이해해봅시다
λ-productios : 예 예 C C b λ C D λ D d ullble vribles C C C C C C C b C D D d 자 이제마지막고개를넘어봅니다.
Methods for Trsformig rmmrs 4 Removig Uit-Productios 정의 6.3 : uit - productio Thm 6.4 T P : CF ithout λ - productios equivletˆ ˆ Tˆ Pˆ ithout y uit - productios pf : obviously removed : * fid such tht ith depedecy put ito Pˆ ll o - uit - productios of P grph y dd to Pˆ. y L y here y y L y 증명도중요하지만예를들어이해합시다.
bc bb bc bb bb bc Uit-Productios : 예 bb bc bc bb 예 useless bc bb bb bc +
문법의변환 : 총정리 Thm 6.5 L : CFL ithout λ CF such tht geertes L & does ot hve y useless productios λ - productios or uit - productios sequece of removl process λ - productios uit - productios 3 useless productios 순서가중요함!!
문법의변환 : Homeork Eercises 6. - 6 : useless productio 의제거연습 - 8 : 문법의변환총정리연습 - 4 3 : 응용문제
Norml Forms Chomsky NF : restrictio o legth of right sides o more th symbols 정의 CF : Chomsky NF C 예 p.65 Emple 6.7 b CNF No CNF
Chomsky Norml Form i CNF ˆ ˆ ˆ ˆ equivlet ith Thm P T L P T CF λ C C C C C T P T P T i pf i i i i i i > if if : to put termil : legth hose termils ll remove : L L Emple 6.8? ˆ ˆ put ito to -side right legth of reduce : ˆ ˆ ˆ ˆ 예 L L D C D D C D C D P P T ii > M
Chomsky Norml Form: 예 Rule CDbE가있다고하자. 이 rule의우측에있는 strig 을생성하는일련의 CNF rule을다음과같이만든다. // 은아래와같이CDbE를 derive 한다. C // C 은 CDbE 를 derive 하도록한다. C CD // D 은 DbE 를 derive 하도록한다. D DE // E 은 be 를 derive 하도록한다. E F E F b // 마지막으로 E 은 be 를 derive 하도록한다.
Chomsky Norml Form: 예예 예 : Cb bb C C Cb c 3 3 4 4 C 5 5 b 3 4 3 b 4 b C C C C D D E E D D CD 3 D 3 b E E c
reibch Norml Form reibch NF : restrictios o positios of T d 정의 CF : reibch NF T cf s grmmr 예 Emples 6.9 6.0 책을한번봅시다
reibch Norml Form: 변환규칙 tep. 다음예와같이새로운 otermil기호 예에서 N 를도입하여다음과같이 frot-recursio rule을다른rule로바꾼다. 예 : CD CDN CD N N tep. Rule의우측이 otermil 예를들면 로시작하고 rule이 termil 기호로시작하는경우를찾아그 rule의 를 rule의우측 strig으로대치한다. 예 : bc cd E.... cdbc EbC cd E.... tep 3. Rule의우측첫번째에위치하지않은 termil기호는다음과같은방법으로새로운 otermil기호로바꾼다. 예 : cdbc cdnc N b
reibch Norml Form: 예 CF: e b tep : ec e C C D D D b tep : tep : tep 3: bec be C DC C D D D D b bec be C DC C D D D becd bed bec be b bec be C DC C D D D becd bed bec be b E e
Norml Forms : Homeork Eercises 6. 4 : Chomsky orml form 으로의변환연습 0 : reibch orml form 으로의변환연습
Membership lgorithm for CF CYK lgorithm: O 3 for membership d prsig origitors: J. Cocke D. H. Youger T. Ksmi grmmr i Chomsky orml form bsic ide: brekig problem ito sequece of smller oes L iff here ij i L j ij : ij} Compute ij Compute ii : ii iff cotis i Compute ij : ij U ij k i i+ L iff C ith j } ik : C C k+ j ith ik C k+ j }
b bbb? 예 } } } } } 55 44 33 55 44 33 b b b } } } : C C Q φ } } } } } } } } 5 5 4 35 4 3 45 34 L?? } } } } : 33 33 3 C C Q
CYK 알고리즘의계산량 계산량 + 3 sets of ij t most terms Ο
CYK 알고리즘 : Homeork Eercises 6.3 : 좀지루하지만한번해봅시다