Chapter 5. Context-Free Language Exercises DS020 오토마타형식언어 Chapter 5. Context-Free Language Exercises September 25, 2003
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
7. Find context-free grammars for the following languages (with ) 힌트 : n을 하나 생성시킬 때마다 m은 두 개 혹은 세 개를 생성시키면 되겠죠? September 25, 2003
8. Find context-free grammars for the following languages (with ) (b) 힌트 : 역시 경우의 수를 나누면 쉽게 풀 수 있는 문제입니다. September 25, 2003
8. Find context-free grammars for the following languages (with ) Sol) S aSc | A A bAcc | λ 힌트 : a가 하나 생성될 때 c도 하나씩 생성시킨 후, b가 하나 생성될 때 c는 두 개씩 생성시키면 됩니다. September 25, 2003
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
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
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
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
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
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