- Prove that the following are not regular languages.
a) ${\{0^n10^n \mid n \geq 1}\}$.
Answer:
- 먼저, Player 2는 $n$을 펌핑 상수(pumping constant)라 정한다.
- 주어진 언어가 정규 언어가 아님을 보이고자 하는 Player 1은 $w=0^n10^n$으로 선택한다. 이때, $w=xyz$, $|w | = 2n+1$일 때, $|xy | \leq n$, $|y | >0$이므로 Player 2가 어떤 방식으로 $w$를 분해하더라도 $y$에 적어도 1개의 $0$을 포함하게 된다.
- Player 1은 Player 2가 어떠한 분해($w$를 $x$, $y$, $z$로 쪼개는 방법) 방법을 제시해도 $y$를 펌핑하면 $1$을 기준으로 앞의 $0$의 개수와 뒤의 $0$의 개수가 같지 않게 되므로 $0^n10^n$이 성립되지 않는다.
따라서, 위 언어는 정규 언어가 아니다.
b)${\{0^n1^m2^n \mid \text{$n$ and $m$ are arbitary integers}}\}$.
Answer:
- 먼저, Player 2는 $n$을 펌핑 상수(pumping constant)라 정한다.
- Player 1은 문자열로 $w= 0^n1^m2^n$를 선택한다. (이때, $w=xyz$, $| w | = 2n+1$일 때, $| xy | \leq n$, $| y | >0$이므로 $y$에 적어도 1개의 $0$을 포함하게 된다.)
- Player 2가 어떠한 방식으로 $w$를 분해하더라도 $y$가 1개 이상의 $0$을 포함하므로, $ xy^i z $는 $i$가 1이 아닐 때 주어진 언어($0^n1^m2^n$)에 속하지 않는다.
따라서, 위 언어는 정규 언어가 아니다.
c) ${\{0^n1^{2n} \mid n \geq 1}\}$.
Answer:
- 먼저, Player 2는 $n$을 펌핑 상수(pumping constant)라 정한다.
- Player 1은 문자열로 $w = 0^n1^{2n}$를 선택한다. 이때, $w=xyz$, $| w | = 2n+1$일 때, $| xy | \leq n$, $| y | >0$이므로 $y$에 적어도 1개의 $0$을 포함하게 된다.
- Player 2가 어떤 방식으로 $w$를 분해하더라도 $y$가 1개 이상의 $0$을 포함하므로, $ xy^i z $는 $i$가 1이 아닐 때 주어진 언어($0^n1^{2n}$)에 속하지 않는다.
따라서, 위 언어는 정규 언어가 아니다.
- Prove that the following are not regular languages.
a) ${\{0^n \mid \text{$n$ is a perfect square}}\}$.
Answer:
- 먼저, Player 2는 $n$을 펌핑 상수(pumping constant)라 정한다.
- Player 1은 문자열로 $w=0^{n^2}$으로 선택한다. 이때, $w=xyz$, $| w | = 2n+1$일 때, $| xy | \leq n$, $| y | >0$이므로 $y$에 적어도 1개의 $0$을 포함하게 된다.
- Player 2가 어떤 방식으로 $w$를 분해하더라도 $y$가 1개 이상, $n$개 이하의 $0$을 포함하게 된다.
- 문자열 $y$의 길이를 $| y | = k$라 하자($1 \le k \le n$). 이 때, 문자열 $| xyyz |$의 길이는 $n^2 + k$이다.
- $n \ge 1$일 때, $n^2 < n^2+1 \le n^2 + k \le n^2 + n < (n+1)^2$이 성립하므로, $| xyyz |$는 perfect square가 아니게 된다. 따라서 $xyyz$는 주어진 언어에 속하지 않는다. (위 부등식에 대한 증명은 생략합니다. Try yourself! Hint: Induction을 사용하여 증명해보세요.)
따라서, 위 언어는 정규 언어가 아니다.
b) ${\{0^n \mid \text{$n$ is a perfect cube }}\}$.
Answer:
- 먼저, Player 2는 $n$을 펌핑 상수(pumping constant)라 정한다.
- Player 1은 문자열로 $w=0^{n^3}$를 선택한다. 이때, $w=xyz$, $| xy | \leq n$, $| y | >0$이므로 $y$에 적어도 1개의 $0$을 포함하게 된다.
- Player 2가 어떤 방식으로 $w$를 분해하더라도 $y$가 1개 이상, $n$개 이하의 $0$을 포함하게 된다.
- 문자열 $y$의 길이를 $| y | = k$라 하자($1 \le k \le n$). 이 때, 문자열 $| xyyz |$의 길이는 $n^3 + k$이다.
- $n \ge 1$일 때, $n^3 < n^3+1 \le n^3 + k \le n^3 + n < (n+1)^3$이 성립하므로, $| xyyz |$는 perfect cube가 아니게 된다. 따라서 $xyyz$는 주어진 언어에 속하지 않는다. (위 부등식에 대한 증명은 생략합니다. Try yourself! Hint: Induction을 사용하여 증명해보세요.)
따라서, 위 언어는 정규 언어가 아니다.
c) ${\{0^n \mid \text{n is a power of 2}}\}$.
Answer:
- 먼저, Player 2는 $n$을 펌핑 상수(pumping constant)라 정한다.
- Player 1은 문자열로 $w=0^{2^n}$를 선택한다. 이때, $w=xyz$, $| xy | \leq n$, $| y | >0$이므로 $y$에 적어도 1개의 $0$을 포함하게 된다.
- 문자열 $y$의 길이를 $| y | = k$라 하자($1 \le k \le n$). 이 때, 문자열 $| xyyz |$의 길이는 $2^n + k$이다.
- $n \ge 1$일 때, $2^n < 2^n +1 \le 2^n + k \le 2^n + n < 2^{n+1}$이 성립하므로, $| xyyz |$는 perfect cube가 아니게 된다. 따라서 $xyyz$는 주어진 언어에 속하지 않는다. (위 부등식에 대한 증명은 생략합니다. Try yourself! Hint: Induction을 사용하여 증명해보세요.)
따라서, 위 언어는 정규 언어가 아니다.
d) The set of string of $0$’s and $1$’s whose length is a perfect square.
Answer: (이 증명은 문제 2-(a)에 대한 증명과 동일하다. 주어진 언어가 정규 언어가 아님을 증명하고자 하는 Player 1이 2-(a)에서와 똑같은 문자열을 제시함으로써 주어진 언어가 정규 언어가 아님을 증명할 수 있기 때문이다.)
- 먼저, Player 2는 $n$을 펌핑 상수(pumping constant)라 정한다.
- Player 1은 문자열로 $w=0^{n^2}$를 선택한다. 이때, $w=xyz$, $| xy | \leq n$, $| y | >0$이므로 $y$에 적어도 1개의 $0$을 포함하게 된다.
- Player 2가 어떤 방식으로 $w$를 분해하더라도 $y$가 1개 이상, $n$개 이하의 $0$을 포함하게 된다.
- 문자열 $y$의 길이를 $| y | = k$라 하자($1 \le k \le n$). 이 때, 문자열 $| xyyz |$의 길이는 $n^2 + k$이다.
- $n \ge 1$일 때, $n^2 < n^2+1 \le n^2 + k \le n^2 + n < (n+1)^2$이 성립하므로, $| xyyz |$는 perfect cube가 아니게 된다. 따라서 $xyyz$는 주어진 언어에 속하지 않는다.
따라서, 위 언어는 정규 언어가 아니다.
- When we try to apply the pumping lemma to a regular language, the adversary wins, and we cannot complete the proof. Show what goes wrong when we choose $L$ to be one of the following languages.
a) ${\{00,11}\}$
Answer:
- Player 2가 상수 3을 펌핑 상수로 제시한다.
- Player 1은 $|w |=3$ 이상인 문자열 $w$을 제시할 수 없다.
(따라서, 주어진 언어가 정규 언어가 아님을 (펌핑 렘마로는) 증명할 수 없다.)
b) $(00+11)^*$
Answer:
- Player 2가 $0$보다 큰 $n$을 펌핑 상수로 제시한다.
- Player 1은 빈 문자열 $\epsilon$이 아닌 어떤 문자열 $w$를 선택해야 하고, 이 문자열은 $00$또는 $11$의 나열로 이루어져야만 한다.
- Player 2는 $w$를 분해하면서, $y$로 $00$또는 $11$을 선택한다.
- 이 경우, Player 1이 모든 가능한 $i$에 대하여 $xy^i z$가 주어진 언어에 속해있는지를 확인하지만 어떤 $i$에 대해서도 $xy^i z$가 주어진 언어에 속하게 된다.
(따라서, 주어진 언어가 정규 언어가 아님을 (펌핑 렘마로는) 증명할 수 없다.)
- Suppose $L$ is a regular language with alphabet $\Sigma$. Given an algorithm to tell whether $L = \Sigma^*$, i.e, all strings over its alphabet.
Answer:
- $L$을 인식하는 DFA로부터 $\overline{L}$($L$의 여집합, $\Sigma^* - L$)을 인식하는 DFA를 만든다. (어떻게? $L$을 인식하는 DFA가 $A$라 하자. $A$의 모든 final state를 non-final state로 바꾸고, 모든 non-final 상태를 final state로 바꾼다)
- 위에서 만들어진 $\overline{L}$에 대한 DFA를 $B$라 하자.
- $B$의 start state로부터 final state에 도달하는 경로가 존재한다면, $\overline{L}$가 인식하는 문자열 $w$가 존재한다.
- $w\in \overline{L} \Rightarrow w \notin L$이므로, $L \ne \Sigma^*$임을 알 수 있다.
- 따라서, DFA $B$의 start state로부터 final state 중 하나라도 도달하는 경로가 존재하는지를 그래프 탐색 알고리즘을 통해 확인한다.
- Give an algorithm to tell whether two regular languages $L_1$ and $L_2$ have at least one string in common.
Answer:
- $L_1,L_2$에 대한 product DFA를 만든다.
- $L_1,L_2$ 둘다 final state인 state가 product DFA의 final state가 된다.
- 이때, product DFA의 start state에서 final state로 도달하는 경로가 존재하는 경우, $L_1,L_2$가 공통으로 가지는 문자열이 존재한다.
6.
state | $0$ | $1$ | |
---|---|---|---|
$\rightarrow$ | $A$ | $B$ | $A$ |
$B$ | $A$ | $C$ | |
$C$ | $D$ | $B$ | |
* | $D$ | $D$ | $A$ |
$E$ | $D$ | $F$ | |
$F$ | $G$ | $E$ | |
$G$ | $F$ | $G$ | |
$H$ | $G$ | $D$ |
a) Draw the table of distinguishabilities for this automaton.
$H$ | $G$ | $F$ | $E$ | $D$ | $C$ | $B$ | |
---|---|---|---|---|---|---|---|
$A$ | X | X | X | x | X | X | |
$B$ | X | X | X | x | X | ||
$C$ | X | X | X | X | |||
$D$ | X | X | X | X | |||
$E$ | X | X | X | ||||
$F$ | X | x | |||||
$G$ | X |
b) Construct the minimum-state equivalent DFA.
state | 0 | 1 | |
---|---|---|---|
$\rightarrow$ | $AG$ | $BF$ | $AG$ |
$BF$ | $AG$ | $CE$ | |
$CE$ | $D$ | $BF$ | |
* | $D$ | $D$ | $AG$ |
$H$ | $AG$ | $D$ |
7.
state | $0$ | $1$ | |
---|---|---|---|
$\rightarrow$ | $A$ | $B$ | $E$ |
$B$ | $C$ | $F$ | |
* | $C$ | $D$ | $H$ |
$D$ | $E$ | $H$ | |
$E$ | $F$ | $I$ | |
* | $F$ | $G$ | $B$ |
$G$ | $H$ | $B$ | |
$H$ | $I$ | $C$ | |
* | $I$ | $A$ | $E$ |
a) Draw the table of distinguishabilities for this automaton.
$I$ | $H$ | $G$ | $F$ | $E$ | $D$ | $C$ | $B$ | |
---|---|---|---|---|---|---|---|---|
$A$ | X | X | X | X | X | X | ||
$B$ | X | X | X | X | X | |||
$C$ | X | X | X | X | ||||
$D$ | X | X | X | X | ||||
$E$ | X | X | X | |||||
$F$ | X | X | ||||||
$G$ | X | X | ||||||
$H$ | X |
B) Construct the minimum-state equivalent DFA.
state | 0 | 1 | |
---|---|---|---|
$AGD$ | $BHE$ | $BHE$ | |
$BHE$ | $CIF$ | $CIF$ | |
* | $CIF$ | $AGD$ | $BHE$ |