Midterm Fall 2014 2014 년 10 월 10 월 21 일화요일오후 1:00 2:30 전산학동 E3-1 1501 호 ( 제 1 공동강의실 ) Prof. Choe, Kwang-Moo : : Grading Result: Problem Total 1 /10 /10 2 /10 /10 /10 /30 3 /5 /10 /15 4 /10 /15 /15 /40 5 /10 /10 /20 6 /10 /5 /15 7 /10 /10 Grade /140 1
1. 이산수학복습 (Review of discrete mathematics) (10 점 ) 기본문자 (vocabulary) 에서정의된문자열 (string) 전체의집합 가 countably infinite 임을증명하시오. Chapter 1-2 TP 18p 를보고 bijective 함수만들어냄 2
2. Regular Language 의이해 ( 총 30 점 ) 아래언어 L 이 regular language 인지아닌지를판별하고, regular 인경우, DFA 나 regular expression 을제시하고, regular language 가아닌경우, pumping lemma 를이용하여증명하시오. 2-1. LL = aa ii bb jj cc kk ii, jj, kk 11, ii + kk = jj (10 점 ) DFA 로표현할수없다. Pumping lemma 로증명 Suppose L can be accepted by an FA, and let n be the integer in the statement of the pumping lemma. Let x = aibjck, i+k=j. Then x L n >= 0, \exist w L such that w >= n w=anbn+mcm, 라하자. x, y, z such that w =xyz, y, xy <=n, y = ai, 1<=i<=n 그런데, xy2z = an+ibn+mcm L 따라서, pumping lemma 에의해 L 은 regular language 가아니다. 3
2-2. LL = {ww aa ww iiii aa FFFFFFFFFFFFFFFFFF nnnnnnnnnnnn. } (10 점 ) Regular 아님. Given number n, find i that is the first Fibonacci number larger than n. And find a Fibonacci number m that is larger than 4i. Then, the difference between m and the next fibonacci number m` is larger than 2n. Therefore, the interval (m, m`) contains at least one x + y * k + z for some k where x + y + z = i and x + y n and y!= 0. Thus, L is not a regular language. 2-3. LL = {aa 2222 bb 3333 ii 00, jj 00} (10 점 ) (aa)*(bbb)* 4
3. Regular Expression 의이해 ( 총 15 점 ) ΣΣ = {00, 11} 일때, 두개의 regular expression 이같은언어를나타냄 (denote) 은 m-dfa 가같음 (isomorphism) 을보여증명할수있다. 이를이용하여, 아래의두개의 regular expression 이같음을, m-dfa 를그려증명하시오. ( 참고 ) RE 를 ε-nfa 로고칠때, 가능한한 state 와 ε-move 의수를줄이시오. 3-1. (00 11) 00 와 (00 + 11) (5 점 ) (00 11) 00 (00 + 11) 문자열을 right to left 방식으로읽는다고생각하자. ε 의경우 : 자명길이가 1 이상인문자열에대해 postfix 가 0 이라면 1 이나오기전까지 0* 로표현가능하다. 그다음문자가 1 이오면다음 1 을만날때까지 0*1 로표현가능하다. 이과정을 recursive 하게하면모든문자열을 (0*1)*0* 로나타낼수있다. 3-2. 1*+(1*01*01*)* 와 (01*0+1)* (10 점 ) 0=a, 1=b 5
4. Minimal state DFA 의이해 ( 총 40 점 ) 4-1. = {00, 11} 일때, (000000 + 111111) (000000 + 000000) 로정의된언어 (language) L 에대하여 minimal state DFA 를그려라. (Hint: RE ε-nfa DFA m-dfa). ( 참고 ) RE 를 ε-nfa 로고칠때, 가능한한 state 와 ε-move 의수를줄이시오. 또한 dead state 는나타내지마시오. (10 점 ) ε-nfa DFA(minimal) 위의 DFA 는 minimal 이다. 왜냐하면모든 state p, q 에대해 p q 이기때문이다. ( 표참조 ) 6
State / input 0 1 q0:{a,d} {,G} {E} q1:{,g} {H} {C,I} q2:{e} empty {F} q3:{h} {J} Empty q4:{c,i} {J} {A,D} q5:{f} {A,D} Empty q6:{j} empty empty 7
4-2. DFA = (Q, Σ, δ, q 0, F) 에대하여다음과같은관계 (relation) 을정의한다. = {(pp, gg) QQ QQ ww ΣΣ, δδ (pp, ww) FF δδ (qq, ww) FF} 관계 는 equivalent relation 이며, equivalent class [qq] 는정규식 (regular expression) 으로표현가능하다. 어떤상태 q 에대하여 [qq] 를정규식으로나타내는방법은 final state 를 q 라두고, final state 를바꾼 DFA 가받아들이는언어를연립정규방정식을푸는방법 ( 교과서 TP Chapter 4, 23-24p) 으로구하면된다. (15 점 ) (1) 4-1 의 DFA 에대하여각 equivalent class [qq] 을구하기위한연립정규방정식을쓰시오. state 가 인경우, 나타내지마시오. (5 점 ) (2) 위연립정규방정식을사용하여모든 equivalent class [qq] 을정규식으로나타내어라. (10 점 ) (1) [A]: A = 0 + 1F + e = 1C C = 1A F = 1G G = 0A []: A = 0 + 1F = 1C + e C = 1A F = 1G G = 0A [C]: 8
A = 0 + 1F = 1C C = 1A + e F = 1G G = 0A [D]: A = 0 + 1F = 0D + 1C C = 1A D = e F = 1G G = 0A [F]: A = 0 + 1F = 1C C = 1A F = 1G + e G = 0A [G]: A = 0 + 1F = 1C C = 1A F = 1G G = 0A + e [E]: A = 0 + 1F = 0D + 1C C = 0E + 1A D = 0E 9
E = e F = 1G G = 0A (2) [A] = (011+110)* [] = (011+110)*0 [C] = (011+110)*01 [D] = (011+110)*00 [E] = (011+110)*(000+010) [F] = (011+110)*1 [G] = (011+110)*11 10
4-3. 다음은어떤 DFA 를연립정규방정식으로나타낸것이다. A = 0 + 1A = 0 + 1C C = 0 + 1D D = 0 + 1A + ε 시작상태 (initial state) 를 A 라고할때, [AA] = εε + 11 + 1111 + (00 + 11) 111111 가됨을보여라. (15 점 ) [AA] 를구하기위해상태 A 를 final state 라둔다. 그러면연립방정식이다음과같이바뀐다. A=0+1A+ε =0+1C C=0+1D D=0+1A 에서 A=D+ ε 이다. 이것을 D=0+1A 에대입하면 D=0+1D+1=C+1 이된다. 이를 C=0+1D 에대입하면 C=0+1C+11 이고따라서 C=+11 이된다. D=C+1 에넣으면 D=+11+1 이되고 A=D+ ε 에의해 A= +11+1+ε 이다. 식 =0+1C 에서 = 0*1C 이고, 이를 C=+11 에대입하면 C= 0*1C+11 이된다. 이식을다시 = 0*1C 에넣게되면 = 0*1(0*1)*11 = (0*1)* 0*111. 따라서 A= +11+1+ε = (0*1)* 0*111 + 11+1+ε 이다. 여기서 (0*1)* 0* = (0+1)* 이므로 A= (0*1)* 0*111 + 11+1+ε = (0+1)* 111 + 11+1+ε. 11
5. Context Free Grammar(CFG) 의이해와표현 ( 총 20 점 ) 5-1. 다음언어의 CFG 를쓰고, 각 non-terminal symbol( 비말단기호 ) 들은각각어떤문자열을만들어내는지설명하시오. (10 점 ) [ 답안 ] S ε a ba 1 A 1 a A 2 A 2 as ba 1 A 2 ba 2 A 1 bs a A1: b 의개수가 a 의개수의 2 배보다하나적은문자열 A2: b 의개수가 a 의개수의 2 배보다 2 개적은문자열 : b 의개수가 a 의개수의 2 배보다하나많은문자열 12
5-2. 5-1 에서쓴 CFG 를이용하여, 다음언어의 CFG 를쓰시오. (10 점 ) [ 답안 ] 5-1 에서 a 와 b 개수바뀜 G = (V, {a,b}, S, P) V = {S, A, 1, 2, 3,, k } P = S ε ba k a 1 A as ba n+1 1 ba k-1 a 2... i ba k-i a i+1... k-1 ba k-(k-1) a k k ba k-1 a k 1 a k-1 2 a 2 k-1 a 1 k 13
6. DFA 와 table filling algorithm 의이해 다음과같이 DFA D 가주어져있다. 각질문에답하여라. ( 총 15 점 ) 6-1. DFA D 에대해 table filling algorithm 을실행할때, 각 iteration 에따른 table 의변화를나타낸것이다. Iteration 마다변한 table 을완성하여라. Iteration 은 table 의위에서부터가로를다확인한다음에아래로진행한다. ( 단, 두 state 가 distinguishable 이면 table 에 d 로표현한다.) (10 점 ) ( 참고 ) 교과서 TP Chapter 4, 20p asis: C D E F 14
change : 1 change : 2 change : 3 change : 4 C D E F C D E F C D E F C D E F 15
change : 5 C D E F 6-2. 6-1) 의 table 을참고하여 DFA D 의 minimal state DFA 를그려라. (5 점 ) 6-1) asis: Iter : 1 Iter : 2 C D E d d d d F d d d d C d D E d d d d F d d d d C d d D E d d d d F d d d d 16
Iter : 3 Iter : 4 Iter : 5 C d d D d E d d d d F d d d d C d d D d d E d d d d F d d d d d C d d D d d E d d d d F d d d d 6-2) 17
7. Mealy Machine 과일반 DFA 의이해 다음 Mealy Machine 의입력문자열이 1+2*2= 일때, 그출력값을구하시오. (5 점 ) MM ee = (QQ, ΣΣ, ΠΠ, δδ, λλ, qq 0 ) QQ = {ss, nn, oo, ff}, ΣΣ = {1,2,3,4, +, =} ΠΠ = {pppppph1, pppppph2, pppppph+, pppppph, cccccccc, pppppppppp} (pp ΠΠ는프로그램블록또는함수 ) δδ = {δδ(ss, 1) = nn, δδ(ss, 2) = nn, δδ(nn, +) = oo, δδ(nn, ) = oo, δδ(oo, 1) = nn, δδ(oo, 2) = nn, δδ(nn, =) = ff} λλ = {λλ(ss, 1) = pppppph1, λλ(ss, 2) = pppppph2, λλ(nn, +) = pppppph+, λλ(nn, ) = pppppph, λλ(oo, 1) = cccccccc, λλ(oo, 2) = cccccccc, λλ(nn, =) = pppppppppp} qq 0 = ss 프로그램블록 ( 함수 ) 설명 ( 괄호안은 Stack 을아는분을위한설명입니다.): 전역변수SS: 빈 list(array)(ordered set) 로초기화됨 (SS = 빈 Stack) 1 + 1 = 2, 1 + 2 = 3, 2 + 1 = 3, 2 + 2 = 4, 1 + 2 = 3, 1 + 4 = 5 1 1 = 1, 1 2 = 2, 2 1 = 2, 2 2 = 4, 3 2 = 6 pppppph1: SS의위 (top) 에 1 를추가, SS. pppppph(1) pppppph2: SS의위에 2 를추가, SS. pppppph(2) pppppph +: SS의위에 + 을추가, SS. pppppph(+) pppppph : SS의위에 * 을추가, SS. pppppph( ) cccccccc: pppppppppp: vv 1 {1,2,3,4}, vv 1 = SS. pppppp() oooo {+, }, oooo = SS. pppppp() vv 2 {1,2,3,4}, vv 2 = SS. pppppp() iiii oooo = + ttheeee pppppph(vv 1 vv 2 ) & oooo = ttheeee pppppph(vv 1 + vv 2 ) SS의제일끝원소를출력 (pppppppppp SS. pppppp()) 4 18