Chapter 7. PUSHDOWN AUTOMATA Exercises

Presentation on theme: "Chapter 7. PUSHDOWN AUTOMATA Exercises"— Presentation transcript:

1 Chapter 7. PUSHDOWN AUTOMATA Exercises
DS020 오토마타형식언어 Chapter 7. PUSHDOWN AUTOMATA Exercises September 25, 2003

2 4. Construct npda’s that accept the following languages on
7.1 NONDETERMINISTIC PUSHDOWN AUTOMATA 4. Construct npda’s that accept the following languages on Solution Start state : q0 Start stack symbol : z Final state : qf p(q0, λ, z) = (qf, z) p(q0, a, z) = (q1, 00z) p(q1, a, 0) = (q1, 000) p(q1, b, 0) = (q2, λ) p(q2, b, 0) = (q2, λ) p(q2, λ, z) = (qf, z) 힌트 : 하나의 a가 두개의 b와 매치되도록 합니다. September 25, 2003

3 7.1 NONDETERMINISTIC PUSHDOWN AUTOMATA
Start state : q0 Start stack symbol : z Final state : qf p(q0, b, z) = (q3, 1z) // b로 시작하는 경우 p(q0, a, z) = (q1, 0z) // a로 시작하는 경우 p(q1, a, 0) = (q1, 00) p(q1, b, 0) = (q2, λ) p(q2, b, 0) = (q2, λ) p(q2, b, z) = (q3, 1z) p(q3, b, 1) = (q3, 11) p(q3, c, 1) = (q4, λ) p(q4, c, 1) = (q4, λ) p(q4, λ, z) = (qf, λ) Solution anbn bmcm 힌트 : a와 b의 개수를 먼저 맞추고, 그 다음 b와 c의 개수를 맞추도록 합시다. September 25, 2003

4 7.1 NONDETERMINISTIC PUSHDOWN AUTOMATA
Start state : q0 Start stack symbol : z Final state : qf p(q0, a, z) = (q1, z) // a로 시작하는 경우 첫 a를 무시 p(q0, b, z) = (q1, 11z) // b로 시작하는 경우 첫 b를 두 개로 계산 p(q1, a, z) = (q1, 0z) p(q1, a, 0) = (q1, 00) p(q1, b, 0) = (q1, λ) p(q1, b, 1) = (q1, 11) p(q1, a, 1) = (q1, λ) p(q1, λ, z) = (qf, z) Solution na(w) = nb(w) 힌트 : a로 시작하는 경우와 b로 시작하는 경우를 따로 생각해서, a로 시작할 때는 하나를 무시해주고, b로 시작할 때는 처음 나오는 b를 두개로 쳐줍시다. September 25, 2003

5 7.1 NONDETERMINISTIC PUSHDOWN AUTOMATA
Start state : q0 Start stack symbol : z Final state : qf Solution p(q0, λ, z) = (qf, z) p(q0, a, z) = (q1, 00z), (q1, 000z) p(q0, b, z) = (q2, 1z) p(q1, a, 0) = (q1, 000), (q1, 0000) p(q1, b, 0) = (q1, λ) p(q1, a, z) = (q1, 00z), (q1, 000z) p(q1, b, z) = (q2, 1z) p(q2, b, 1) = (q2, 11) p(q2, a, 1) = (q3, λ) p(q3, λ, 1) = (q2, λ), (q4, λ) p(q4, λ, 1) = (q2, λ) p(q2, a, z) = (q1, 00z), (q1, 000z) p(q2, b, z) = (q2, 1z) p(q3, λ, z) = (q1, 0z), (q1, 00z) p(q4, λ, z) = (q1, 0z) p(q1, λ, z) = (qf, z) p(q2, λ, z) = (qf, z) q1과 q2는 꼭 나눌 필요가 없는것 같군요.. 그 이유는 stack의 top으로 구별가능하기 때문입니다. 힌트 : 하나의 a에 대하여 2개 혹은 3개의 b와 매치가 되도록 해봅시다. September 25, 2003

6 설명 p(q0, λ, z) = (qf, z) // empty string  final
p(q0, a, z) = (q1, 00z), (q1, 000z) // 시작 입력이 a인 경우 p(q0, b, z) = (q2, 1z) // 시작 입력이 b인 경우 p(q1, a, 0) = (q1, 000), (q1, 0000) // a가 더 많은데, a가 나오면 2개 혹은 3개 추가 p(q1, b, 0) = (q1, λ) // a가 더 많은데, b가 나오면 a 한 개 감소 p(q1, a, z) = (q1, 00z), (q1, 000z) // 스택이 바닥일 때 a가 나온 경우 p(q1, b, z) = (q2, 1z) // 스택이 바닥일 때 b가 나온 경우 p(q2, b, 1) = (q2, 11) // b가 더 많은데 b가 나온 경우 b 한 개 추가 p(q2, a, 1) = (q3, λ) // b가 더 많은데 a가 나온경우 2개 혹은 3개를 // 빼야 하므로 일단 한 개 빼고 q3로 이동 p(q3, λ, 1) = (q2, λ), (q4, λ) // 아직 b가 많은 경우 하나 더 빼려면 q2로, // 두 개 더 빼려면 q4로 이동 p(q4, λ, 1) = (q2, λ) // 아직 b가 많으므로 하나 더 빼고 다시 q2로 이동 p(q2, a, z) = (q1, 00z), (q1, 000z) // 스택이 바닥일 때 a가 나온 경우 p(q2, b, z) = (q2, 1z) // 스택이 바닥일 때 b가 나온 경우 p(q3, λ, z) = (q1, 0z), (q1, 00z) // 빼야 할 a가 1개 혹은 2개 남았을 때 스택이 바닥 // 인 경우 p(q4, λ, z) = (q1, 0z) // 빼야 할 a가 1개 남았을 때 스택이 바닥인 경우 p(q1, λ, z) = (qf, z) // 입력을 다 소비하고 스택이 바닥인 경우 p(q2, λ, z) = (qf, z) // 입력을 다 소비하고 스택이 바닥인 경우 September 25, 2003 스택의 역할 : a의 개수가 많은지 b의 개수가 많은지 비교 단, a 하나는 2개 혹은 3개로 고려합니다.

7 7.1 NONDETERMINISTIC PUSHDOWN AUTOMATA
14. Find an npda with no more than two internal states that accepts the language L(aa*ba*). Start state : q0 Start stack symbol : z Final state : qf p(q0, a, z) = (q0, 1) p(q0, a, 1) = (q0, 1) p(q0, b, 1) = (q0, 2) p(q0, a, 2) = (q0, 2) p(q0, λ, 2) = (qf, 2) Solution 힌트 : state 대신 stack symbol을 이용하여 상태를 구분할 수 있습니다. September 25, 2003

8 7.2 PUSHDOWN AUTOMATA AND CONTEXT-FREE LANGUAGES
3. Construct an npda that accepts the language generated by the grammar Start state : q0 Start stack symbol : z Final state : qf p(q0, a, z) = (q1, z) // 처음 나오는 a를 무시 p(q1, a, z) = (q2, z) // 두번 째 나오는 a를 무시 p(q2, b, z) = (qf, z) p(q2, a, z) = (q2, 00z) p(q2, a, 0) = (q2, 000) p(q2, b, 0) = (q3, 0) // 처음 나오는 b를 무시 p(q3, b, 0) = (q3, λ) p(q3, λ, z) = (qf, z) Solution 힌트 : aa와 b를 무시하면 나머지는 anb2n을 구성하는 문제이군요. September 25, 2003

9 7.2 PUSHDOWN AUTOMATA AND CONTEXT-FREE LANGUAGES
5. Construct an npda corresponding to the grammar S → aABB|aAA, A→ aBB|a, B→ bBB|A. Start state : q0 Start stack symbol : z Final state : qf p(q0, λ, z) = (q1, Sz) p(q1, a, S) = (q1, ABB), (q1, AA) p(q1, a, A) = (q1, BB), (q1, λ) p(q1, b, B) = (q1, BB) p(q1, λ, B) = (q1, A) p(q1, λ, z) = (qf, z) Solution September 25, 2003

10 7.2 PUSHDOWN AUTOMATA AND CONTEXT-FREE LANGUAGES
15. Find a context-free grammar that generates the language accepted by the npda , with transitions Solution Step 1) 주어진 NPDA는 PDA  CFG 기법의 조건 2는 만족시키지만, 조건 1은 만족시키지 못한다. 따라서 equivalent PDA로 수정이 필요하다. 단 하나의 final state와 stack이 비어야만 final state로 갈 수 있도록 고쳐보면, Start state : q0, final state : q3, start stack symbol : z p(q0, a, z) = (q0 Az) p(q0, b, A) = (q2, λ) p(q2, λ, z) = (q0, Az) p(q0, a, A) = (q1, λ) p(q1, λ, z) = (q3, λ) September 25, 2003

11 Step 2) 교과서의 정리방법을 그대로 따라서 정리한다.
편의상 q0zq0 는 z00, q0Aq2 는 A02 인 식으로 표현하면 A02  b, A01  a, z13  λ Z00  aA00z00 | aA01z10 | aA02z20 | aA03z30 Z01  aA00z01 | aA01z11 | aA02z21 | aA03z31 Z02  aA00z02 | aA01z12 | aA02z22 | aA03z32 Z03  aA00z03 | aA01z13 | aA02z23 | aA03z33 Z20  A00z00 | A01z10 | A02z20 | A03z30 Z21  A00z01 | A01z11 | A02z21 | A03z31 Z22  A00z02 | A01z12 | A02z22 | A03z32 Z23  A00z03 | A01z13 | A02z23 | A03z33 Step 3) 존재하지 않는 non-terminal을 제거하고, 편의상 다음과 같이 symbol들을 변환합시다. z03  S, z00  A, z01  B, z02  C z20  D, z21  E, z22  F, z23  G September 25, 2003

12 Step 5) D, E, F는 useless이므로 삭제하고, 관련된 A, B, C도 지우면,
S  aa | abG A  abD B  abE C  abF D  bD E  bE F  bF G  a | bG Step 5) D, E, F는 useless이므로 삭제하고, 관련된 A, B, C도 지우면, S  aa | abG G  a | bG September 25, 2003

13 1. Show that is a deterministic context-free language.
7.3 DETERMINISTIC PUSHDOWN AUTOMATA AND DETERMINISTIC CONTEXT-FREE LANGUAGES 1. Show that is a deterministic context-free language. Start state : q0 Start stack symbol : z Final state : q0 p(q0, a, z) = (q1, 00z) p(q1, a, 0) = (q1, 000) p(q1, b, 0) = (q2, λ) p(q2, b, 0) = (q2, λ) p(q2, λ, z) = (q0, λ) Solution September 25, 2003

14 8. Is the language L={anbm:n=m or n=m+2} deterministic?
7.3 DETERMINISTIC PUSHDOWN AUTOMATA AND DETERMINISTIC CONTEXT-FREE LANGUAGES 8. Is the language L={anbm:n=m or n=m+2} deterministic? Start state : q0 Start stack symbol : z Final state : {q0, q2, q5} p(q0, a, z) = (q1, z) // q1 : n = m + 1 p(q1, a, z) = (q2, z) // q2 : n = m + 2 p(q1, b, z) = (q0, λ) // q0 : n = m p(q2, a, z) = (q3, 0z) // q3 : n > m+2 p(q2, b, z) = (q6, λ) p(q3, a, 0) = (q3, 00) p(q3, b, 0) = (q4, λ) // q4 : n > m+2 p(q4, b, 0) = (q4, λ) p(q4, λ, z) = (q5, z) // q5 : n = m + 2 p(q5, b, z) = (q6, z) // q6 : n = m + 1 p(q6, b, z) = (q0, λ) Solution September 25, 2003

15 7.4 GRAMMARS FOR DETERMINISTIC CONTEXT-FREE LANGUAGES
8. Let G be a context-free grammar in Grebach normal form. Describe an algorithm which, for any given k, determines whether or not G is an LL(k) grammar. September 25, 2003

16 9. Give LL grammars for the following languages, assuming
7.4 GRAMMARS FOR DETERMINISTIC CONTEXT-FREE LANGUAGES 9. Give LL grammars for the following languages, assuming September 25, 2003