DS020 오토마타형식언어 Chapter 6. Simplification of Context-Free Grammars and Normal Forms Exercises October 16, 2003.

Presentation on theme: "DS020 오토마타형식언어 Chapter 6. Simplification of Context-Free Grammars and Normal Forms Exercises October 16, 2003."— Presentation transcript:

1 DS020 오토마타형식언어 Chapter 6. Simplification of Context-Free Grammars and Normal Forms Exercises October 16, 2003

2 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

3 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

4 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

5 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 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

7 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