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

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

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

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

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

설명 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.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

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

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

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

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

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

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

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

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

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