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)$를 상태 전이도로 나타내세요.
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\} $
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
6. 정규 표현식 $10 + (0+11)0^*+ 1$을 인식하는 최소화된 DFA를 상태 전이도로 나타내세요.
- NFA
- DFA
- 최소화된 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 |
- 상태 전이도
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)^*$