DS020 오토마타형식언어 Chapter 6. Simplification of Context-Free Grammars and Normal Forms Exercises October 16, 2003
6.1 METHODS FOR TRANSFORMING GRAMMARS 6. Eliminate useless productions from S → a | aA | B | C, A → aB | λ, B → Aa, C → cCD, D → ddd. Solution) S a | aA | B A aB | λ B Aa 1) C cCD에서 우측의 C 는 끝나지 않으므로 제거시킵니다. 2) C가 제거되면 D는 도달할 수 없기 때문에 제거하고 S C도 제거합니다. 힌트 : 시작할 수 없거나 끝나지 않는 변수를 찾아봅시다. October 16, 2003
6.1 METHODS FOR TRANSFORMING GRAMMARS 8. Remove all unit-productions, all useless productions, and all λ-productions from the grammar S → aA | aBB, A → aaA | λ, B → bB | bbC, C → B. Solution) S aA | a A aaA | aa 1) B bB | bbC와 C B에서 B와 C는 끝나지 않는 변수가 되므로 제거합니다 2) B가 제거되었으므로 S aBB를 제거합니다. 3) λ-production을 제거하는 기법을 사용하여 답을 구합니다. 힌트 : 끝나지 않는 변수를 먼저 제거해 주는 것이 좋을 것 같군요 October 16, 2003
6.1 METHODS FOR TRANSFORMING GRAMMARS 23. Use the result of the preceding exercise to rewrite the grammar A → Aa | aBc | λ, B → Bb | bc. so that it no longer has productions of the form A → Ax or B → Bx. Solution) A aBc | λ | aBcX | X X aX | a B bc | bcY Y b | bY 힌트 : 연습문제 22의 결과를 그대로 이용해 봅시다. October 16, 2003
6.2 TWO IMPORTANT NORMAL FORMS 4. Transform the grammar with productions S → abAB, A → bAB | λ, B → BAa | A | λ. into Chomsky normal form. 3) 촘스키 형태로 변경 S CD | EA | EB | EF A b | DA | DB | DF B a | AC | BC | GC | b | DA | DB | DF C a D b E CD F AB G BA Solution) 1) λ production 제거 S ab | abA | abB | abAB A b | bA | bB | bAB B a | Aa | Ba | BAa | A 2) unit production 제거 B a | Aa | Ba | Baa | b | bA | bB | bAB S, A는 위와 동일 힌트 : 일단 λ production와 unit production을 제거해봅시다. October 16, 2003
6.2 TWO IMPORTANT NORMAL FORMS 10. Convert the grammar S → aBb | bSa | a | b into Greibach normal form. Solution) S aSD | bSC | a | b C a D b 힌트 : λ production이 없으니 쉽게 풀리는군요. ^^ October 16, 2003
6.3 A MEMBERSHIP ALGORITHM FOR CONTEXT-FREE GRAMMARS 1. Use the CYK algorithm to determine whether the strings aabb, aabba, and abbbb are in the language generated by the grammar in Example 6.11 October 16, 2003