Chapter 5. Context-Free Language Exercises

Presentation on theme: "Chapter 5. Context-Free Language Exercises"— Presentation transcript:

1 Chapter 5. Context-Free Language Exercises
DS020 오토마타형식언어 Chapter 5. Context-Free Language Exercises September 25, 2003

2 7. Find context-free grammars for the following languages (with )
(b) Sol) S  S1 | S2 S1  a S1 b | A A  aA | λ // n 이 m-1보다 큰 경우 S2  a S2 b | B B  bB | bb // n이 m-1보다 작은 경우 힌트 : n이 m-1보다 큰 경우와 작은 경우로 나누어 생각해 봅시다. September 25, 2003

3 7. Find context-free grammars for the following languages (with )
힌트 : n을 하나 생성시킬 때마다 m은 두 개 혹은 세 개를 생성시키면 되겠죠? September 25, 2003

4 8. Find context-free grammars for the following languages (with )
(b) 힌트 : 역시 경우의 수를 나누면 쉽게 풀 수 있는 문제입니다. September 25, 2003

5 8. Find context-free grammars for the following languages (with )
Sol) S  aSc | A A  bAcc | λ 힌트 : a가 하나 생성될 때 c도 하나씩 생성시킨 후, b가 하나 생성될 때 c는 두 개씩 생성시키면 됩니다. September 25, 2003

6 10. Find a context-free grammar for for the language .
5.1 CONTEXT-FREE GRAMMARS 10. Find a context-free grammar for for the language Sol) S  aAb // n은 1 이상이기 때문에 S 대신 A A  aAb | B // 먼저 바깥쪽을 처리한 후 B  aBa | bBb | λ // 안쪽을 처리 힌트 : 바깥쪽의 anbn과 안쪽의 wwR을 따로 생각하면 되겠군요. September 25, 2003

7 14. Show that the following language is context-free.
5.1 CONTEXT-FREE GRAMMARS 14. Show that the following language is context-free. 힌트 : v와 vR 사이에 껴있는 w만 잘 처리하면 쉽게 풀리는 문제입니다. September 25, 2003

8 5.1 CONTEXT-FREE GRAMMARS
22. Find a context-free grammar for the set of all regular expressions on the alphabet {a, b}. September 25, 2003

9 1. Find an s-grammar for . S  aA | b A  aB B  aB | b
5.2 PARSING AND AMBIGUITY 1. Find an s-grammar for S  aA | b A  aB B  aB | b 힌트 : s-grammar의 제약조건에 유의하면서 만들어 봅시다. September 25, 2003

10 13. Show that the following grammar is ambiguous.
5.2 PARSING AND AMBIGUITY 13. Show that the following grammar is ambiguous. 힌트 : ambiguous – 한 문자를 유도하는 2개 이상의 derivation tree가 존재. abab를 유도하는 서로 다른 두 개의 derivation tree를 만들어 봅시다 September 25, 2003

11 5.3 CONTEXT-FREE GRAMMARS AND PROGRAMMING LANGUAGES
5. Give a definition of the correct form of the if-else statement in C. September 25, 2003