Formal Language and Automata Homework 4 Answer

       

  1. 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}$)에 속하지 않는다.

따라서, 위 언어는 정규 언어가 아니다.    

  1. 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$는 주어진 언어에 속하지 않는다.

따라서, 위 언어는 정규 언어가 아니다.

   

  1. 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$가 주어진 언어에 속하게 된다.

(따라서, 주어진 언어가 정규 언어가 아님을 (펌핑 렘마로는) 증명할 수 없다.)

   

  1. 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 중 하나라도 도달하는 경로가 존재하는지를 그래프 탐색 알고리즘을 통해 확인한다.

   

  1. 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$