Compiler Design 3rd Homework Solution

       

1. 두 언어 $L_1 = \{a, b\}$와 $L_2 =\{b, c\}$가 주어졌을 때, 다음을 구하시오.

1-1. $ L_1L_2 = \{ab,ac,bb,bc\} $

1-2. $L_1^2 = \{aa,ab,ba,bb\} $이므로, $ L_1^3 = L_1L_1^2 = \{aaa,aab,aba,abb,baa,bab,bba,bbb\} $

1-3. $L_1 \cup L_2 = \{a,b,c\} $

1-4. $ L_2 \cdot \{\epsilon\} = L_2 = \{b,c\} $

   

2. 다음 형식 문법 $G$가 촘스키 위계 상의 네 종류의 문법 중 어디에 속하는지 판단하고, 생성하는 언어가 무엇인지 설명하세요.
  • 문법의 갈래: Type-3 문법, 정규문법
  • 생성 언어는 다음 두 타입의 문자열들을 포함한다: 1) 0개 이상의 $a$ 이후 1개 이상의 $b$ 이후 $a$ 또는 $b$로 끝나는 문자열, 2) $a$ 하나 또는 세 개 이상의 $a$로 이루어진 문자열

   

3. 다음과 같이 정의된 FA $M = (Q, \Sigma, \delta, q_0, F)$를 상태 전이도로 나타내세요.
q₁ q₂ q₀ start a a a a b b a a

3-1. 문장 $bbbaaa$가 $M$에 의해 인식되는지 확인해보세요.

$\delta(q_0,b) = q_0$

$\delta(q_0,b) = q_0$

$\delta(q_0,b) = q_0$

$\delta(q_0,a) = q_1$

$\delta(q_1,a) = q_0$

$\delta(q_0,a) = q_2$

그러므로($\therefore$), 문자열 $bbbaaa$는 $M$에 의해 인식된다.

 

3-2. FA $M$이 인식하는 언어 $L(M)$을 정규 표현식으로 나타내세요.

$q_0=S,\, q_1=A, \, q_2=B$

$S \rightarrow aA \mid aB \mid bS$

$A \rightarrow aS\mid aA$

$B \rightarrow aS\mid aB\mid bA\mid \epsilon$

$S=aA+aB+bS$

$A = aS+aA = a^+S$

$B = aS+aB+bA+\epsilon = aS+ba^+S+aB+\epsilon = aB+(ba^++a)S+\epsilon = a^*((ba^++a)S+\epsilon)$

$S = aA+aB+bS$

$\quad = bS + aa^+S + a^+((ba^++a)S+\epsilon)$

$\quad = (b + a^+a + a^+(ba^++a))S+a^+$

$\quad = (b + a^+a + a^+(ba^++a))^*a^+)$

   

4. 다음의 NFA를 DFA로 변환하여 상태 전이도로 나타내세요.

$\delta (\{q_0\}, a) = \{q_1, q_2\} $

$\delta (\{q_0\}, b) = \{q_1\} $

$\delta (\{q_1, q_2\}, a) = \{q_0\} $

$\delta (\{q_1, q_2\}, b) = \{q_0, q_2\} $

$\delta (\{q_1\}, a) = \emptyset $

$\delta (\{q_1\}, b) = \{q_0\} $

$\delta (\{q_0, q_2\}, a) = \{q_0, q_1, q_2\} $

$\delta (\{q_0, q_2\}, b) = \{q_1, q_2\} $

$\delta (\{q_0, q_1, q_2\}, a) = \{q_0, q_1, q_2\} $

$\delta (\{q_0, q_1, q_2\}, b) = \{q_0, q_1, q_2\} $

q₀ q₁,q₂ q₁ q₀,q₂ q₀,q₁,q₂ a a b b b a b a,b start

   

5. 다음의 DFA를 최소화된 DFA로 변환하여 상태 전이도로 나타내세요.
입력 1 2
q2 q3 q4 q5 q0 q1
a 1 1 1 1 2 2
b 2 1 1 2 1 1
입력 1 2 3
q3 q4 q2 q5 q0 q1
a 1 1 2 2 3 3
b 2 2 3 3 1 1
  • 최소화된 DFA
q₀ q₂ q₃ start a b a b a b
6. 정규 표현식 $10 + (0+11)0^*+ 1$을 인식하는 최소화된 DFA를 상태 전이도로 나타내세요.
  • NFA
q₀ q₁ q₂ q₃ q₄ q₅ q₇ q₆ q₈ q₉ q₁₀ q₁₁ 1 start 0 1 ε ε 0 ε ε 0 ε 1 1 ε

 

  • DFA
q₀,q₄,q₅,q₇ q₁,q₃,q₈ q₆,q₁₀,q₁₁ q₁₁ q₂ q₉,q₁₀,q₁₁ q₁₁ start 0 1 0 0 0 1 0 0

 

  • 최소화된 DFA
    • $\{q_0,q_4,q_5,q_7\} = p_0$
    • $\{q_6,q_{10},q_{11}\} = p_1$
    • $\{q_1,q_3,q_8\} = p_2$
    • $\{q_{11}\} = p_3$
    • $\{q_{2}\} = p_4$
    • $\{q_9,q_{10},q_{11}\} = p_5$
입력 1 2 3
p0 p1 p2 p3 p4 p5 ε
0 2 2 2 2 3 2
1 2 3 2 3 3 3
입력 1 2 3 4 5
p0 p1 p3 p5 p2 p4 ε
0 2 2 2 2 4 5
1 3 5 5 5 2 5

 

  • 상태 전이도
p₀ p₁,p₃,p₅ p₂ p₄ start 0 0 1 1 0
7. 다음 문법의 언어를 정규 표현식으로 나타내세요.

정규 표현 방정식을 풀면,

$S=aA+bS, \, A=bS+aB, \, B=aB+bB+\epsilon$

$B = aB+bB+\epsilon = (a+b)B+\epsilon = (a+b)^*$

$S = b^*aA$

$\quad = b^* a(bS+aB)$

$\quad = b^* abS+b^* aaB$

$\quad = b^* abS+b^* aa(a+b)^*$

$\quad = (b^* ab)^* b^* aa(a+b)^*$