Theory of Computation Homework 3 Answer

       

  1. Begin with the grammar :

$S \rightarrow ASB \mid \epsilon$

$A \rightarrow aAS \mid a$

$B\rightarrow SbS \mid A \mid bb$

Solution:

a) Eliminate $\epsilon$-productions.

$S \rightarrow ASB \mid AB$

$A \rightarrow aAS \mid aA \mid a$

$B \rightarrow SbS \mid Sb \mid bS \mid b \mid A \mid bb$

b) Eliminate any unit productions in the resulting grammar.

$S \rightarrow ASB \mid AB$

$A \rightarrow aAS \mid aA \mid a$

$B \rightarrow Sbs \mid Sb \mid bS \mid b \mid bb \mid aAS \mid aA \mid a$

c) Eliminate useless symbols in the resulting grammar.

$S \rightarrow ASB \mid AB$

$A \rightarrow aAS \mid aA \mid a$

$B \rightarrow Sbs \mid Sb \mid bS \mid b \mid bb \mid aAS \mid aA \mid a$

d) Put the resulting grammar into Chomsky Normal Form.

$S \rightarrow AE \mid AB$

$A \rightarrow CF \mid CA \mid a$

$B \rightarrow SG \mid SD \mid DS \mid b \mid DD \mid CF \mid CA \mid a$

$C \rightarrow a$

$D \rightarrow b$

$E \rightarrow SB$

$F \rightarrow AS$

$G \rightarrow DS$

   

  1. Repeat Problem 1 for the following grammar :

$S \rightarrow 0A0 \mid 1B1 \mid BB$

$A \rightarrow C$

$B \rightarrow S \mid A$

$C \rightarrow S \mid \epsilon$

Solution:

a) Eliminate $\epsilon$-productions.

$S \rightarrow 0A0 \mid 00 \mid 1B1 \mid 11 \mid BB \mid B$

$A \rightarrow C$

$B \rightarrow S \mid A$

$C \rightarrow S$

b) Eliminate any unit productions in the resulting grammar.

$S \rightarrow 0A0 \mid 00 \mid 1B1 \mid 11 \mid BB$

$A \rightarrow 0A0 \mid 00 \mid 1B1 \mid 11 \mid BB$

$B \rightarrow 0A0 \mid 00 \mid 1B1 \mid 11 \mid BB$

$C \rightarrow 0A0 \mid 00 \mid 1B1 \mid 11 \mid BB$

c) Eliminate useless symbols in the resulting grammar.

$S \rightarrow 0A0 \mid 00 \mid 1B1 \mid 11 \mid BB$

$A \rightarrow 0A0 \mid 00 \mid 1B1 \mid 11 \mid BB$

$B \rightarrow 0A0 \mid 00 \mid 1B1 \mid 11 \mid BB$

d) Put the resulting grammar into Chomsky Normal Form.

$S \rightarrow QY \mid YY \mid TX \mid XX \mid BB$

$Q \rightarrow YA$

$T \rightarrow XB$

$X \rightarrow 1$

$Y \rightarrow 0$

   

  1. Repeat Problem 1 for the following grammar:

$S \rightarrow AAA\mid B$

$A\rightarrow aA \mid B$

$B\rightarrow \epsilon$

Solution:

a) Eliminate $\epsilon$-productions.

$S \rightarrow AAA \mid AA \mid A$

$A \rightarrow aA \mid a$

b) Eliminate any unit productions in the resulting grammar.

$S \rightarrow AAA \mid AA \mid aA \mid a$

$A \rightarrow aA \mid a$

c) Eliminate useless symbols in the resulting grammar.

$S \rightarrow AAA \mid AA \mid aA \mid a$

$A \rightarrow aA \mid a$

d) Put the resulting grammar into Chomsky Normal Form.

$S \rightarrow AC \mid AA \mid BA \mid a$

$A \rightarrow BA \mid a$

$ B \rightarrow a$

$C \rightarrow AA$

   

  1. Let $G$ be an $\epsilon$-production-free grammar whose total length of production bodies is $n$. We convert $G$ to CNF.

a) Show that the CNF grammar has at most $O(n^2)$ productions.

CFG를 CNF로 변환하는 과정은 두 단계로 나뉜다. 첫번째, RHS에 두 개 이상의 심볼이 있고 terminal 심볼이 존재할 때 해당 terminal을 새로운 non-terminal로 부터 유도하는 production을 생성한다. 두번째, RHS에 세 개 이상의 심볼이 존재할때, chain rule을 통해 여러 production으로 분해한다. 따라서 CNF Grammar에는 $A \rightarrow BC$, $X\rightarrow a$의 두 가지 형태의 production이 존재한다.

첫번째 과정에서 생성되는 production은 유한한 terminal 심볼의 개수에 비례하고, 두번째 과정에서 생성되는 nonterminal들은 production body들의 길이인 $n$을 최대 $n-1$로 분해하기에 $n$과 비례한다. 따라서 변환된 CNF grammar가 최대가 되었을 때는, 두번째 과정에서 생성되는 nontermianl에 대한 production이 기존의 production bodies의 개수인 n개 씩 추가가 되었을때 이므로 $O(n^2)$라고 표현 할 수 있다.

b) Show that it is possible for the CNF grammar to have a number of productions proportional to $n^2$. Hint: Consider the construction that eliminates unit productions.

다음과 같은 CFG를 가진 $L$을 살펴보자.

$A \rightarrow A_1A_2 \mid A_3A_4 \mid A_5A_6 \mid A_7A_8 \mid A_9A_{10} \mid …$

$B\rightarrow C$

$C\rightarrow D$

$…$

$Z\rightarrow A$

$L$을 CNF로 변환하는 과정속에서 unit prouctions를 제거한다면 다음과 같이 변화한다.

$A \rightarrow A_1A_2 \mid A_3A_4 \mid A_5A_6 \mid A_7A_8 \mid A_9A_{10} \mid …$

$B\rightarrow A_1A_2 \mid A_3A_4 \mid A_5A_6 \mid A_7A_8 \mid A_9A_{10} \mid …$

$C\rightarrow A_1A_2 \mid A_3A_4 \mid A_5A_6 \mid A_7A_8 \mid A_9A_{10} \mid …$

$…$

$Z\rightarrow A_1A_2 \mid A_3A_4 \mid A_5A_6 \mid A_7A_8 \mid A_9A_{10} \mid …$

이때 원래의 CFG의 productions를 n이라고 지정하였을 때, chain rule을 통해서 새로이 생성되는 논터미널의 개수가 n에 비례하므로 productoin의 개수는 $n^2$에 비례한다.

따라서 CNF가 $n^2$의 production들을 가질 수 있다는 사실을 확인 할 수 있다.

   

  1. Use the CFL pumping lemma to show each of these languages not to be context-free:

a) ${\{a^i b^j c^k \mid i<j<k }\}$

Consider $n < i$ and $z = uvwxy$. $\vert vx \vert > 0$ and $\vert vwx \vert \le n$ implies that $vwx$ can contains at most two alphabet because of $j > n$.

In first case, $vwx$ has at least one a, therefore $vwx$ can only be a substring of $a^i b^j$. The number of $a$ can exceed the number of $c$ when $p$ goes up in $uv^p wx^p y$ . Thus this case is impossible . In second case, $vwx$ has no a, therefore $vwx$ can only be a substring of $b^j c^k$. The number of $a$ can exceed the number of $c$ when $uv^0 wx^0 y$ since $ \vert c \vert < k$ while $ \vert a \vert = i$. Thus this case is impossible .

Thus, ${\{a^i b^j c^k \mid i<j<k }\}$ is not CFL.

b) ${\{0^i 1^j \mid j = i^2 }\}$

Consider $n = i$ and $z = 0^n 1^{n^2}.$ Since $ \vert z \vert > n$, there are $z = uvwxy$ , $ \vert vx \vert > 0$, and $ \vert vwx \vert \le n$.

In first case, $vwx$ has only $0$s. Then $ \vert 0 \vert $ will change with pumping while $ \vert 1 \vert = n^2$. Thus this case is impossible. In second case, $vwx$ has both $0$s and $1$s. If $v$ has one $0$ and $x$ has one $1$, and pumped once, then they will have $n+1$ $0$s and $n^2 + 1$ $1$s. This case is impossible because $(n+1)^2 \ne n^2 +1$.

In third case, $vwx$ has only $1$s. Then, $ \vert 1 \vert $ will change with pumping while $ \vert 0 \vert = n$. Thus this case is impossible.

Thus, ${\{a^i b^j c^k \mid i<j<k}\}$ is not CFL.

   

  1. When we try to apply the pumping lemma to a CFL, 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) ${\{0^n 1^n \mid n \geq 1 }\}$

  • Player 2가 상수 1보다 큰 n을 펌핑 상수로 제시한다.

  • Player 1은 n보다 같거나 큰 어떤 문자열 $w$을 선택해야하고, 이 문자열은 0의 나열과 1의 나열의 연결로 이루어져야만 한다.

  • Player 2는 $w$를 분해하면서, $v$는 0, $x$는 1로 선택한다.

  • Player 1은 모든 가능한 i에 대해서 $uv^i wx^i y$가 주어진 언어에 속해 있는지를 확인하지만 어떤 $i$에 대해서도 $uv^i wx^i y$가 주어진 언어에 속하게 된다.

따라서, 주어진 언어가 CFL이 아님을 pumping lemma로는 증명할 수 없다.

​ b) The set of palindromes over alphabet ${\{0,1}\}$.

​ Example : $00100,11,10101∈L$ and $110,01101,111000∉L$

  • Player 2가 n을 펌핑 상수로 제시한다.

  • Player 1은 n보다 같거나 큰 어떤 문자열 $w$를 선택해야 하고, 이 문자열은 $\beta \beta^R$ 혹은 $\beta a\beta^R$ 형태이다. ($a \in \Sigma, \beta \in \Sigma^*$)

  • Player 2는 $w$를 분해하면서 $v$는 $\beta$의 마지막 심볼, $v$는 $\beta^R$의 첫번째 심볼으로 선택한다.

  • Player 1은 모든 가능한 i에 대해서 $uv^i wx^i y$가 주어진 언어에 속해 있는지를 확인하지만 어떤 $i$에 대해서도 $uv^i wx^i y$가 주어진 언어에 속하게 된다.

따라서, 주어진 언어가 CFL이 아님을 pumping lemma로는 증명할 수 없다.

   

  1. Show that the CFL’s are closed under the following operations :

a) $init(L) = {\{ w \mid }$ for some $x$, $wx$ is in ${L}\}$

CFL인 모든 $L$는 CNF형태로 변환할 수 있으며, $S \rightarrow AB$ 혹은 $X \rightarrow a$ 형태의 production들만 존재한다. 따라서 CNF을 일반화하여 표현하면 다음과 같은 꼴로 나타낼 수 있다.

$S \rightarrow A_1X_1$

$X_1 \rightarrow A_2X_2$

$X_2 \rightarrow A_3X_3$

$…$

$X_{i-1} \rightarrow A_iX_i$

$A_1 \rightarrow a_1$

$A_2 \rightarrow a_2$

$…$

$A_i \rightarrow a_i$

$X_i \rightarrow a_{i+1}$

이때, $init(L)$은 다음과 같이 표현이 가능하다.

$S \rightarrow A_1X_1 \mid A_1 \mid \epsilon$

$X_1 \rightarrow A_2X_2 \mid A_2$

$X_2 \rightarrow A_3X_3 \mid A_3$

$…$

$X_{i-1} \rightarrow A_iX_i \mid A_i$

$A_1 \rightarrow a_1$

$A_2 \rightarrow a_2$

$…$

$A_i \rightarrow a_i$

$X_i \rightarrow a_{i+1}$

이처럼 start state가 LHS에 속해 있는 production의 RHS에 $\epsilon$을 추가해주고, RHS에 두 non-terminal이 있는 모든 production에 RHS의 첫번째 non-terminal을 추가한다.

해당 변형을 통해 모든 $L$에 대해 CFG의 형식을 만족하는 $init(L)$을 생성할 수 있기에 $init$ 연산에 CFL은 닫혀있다.

b) The operation $L/a$, the quotient of $L$ and $a$, is the set of strings $w$ such that $wa$ is in $L$. For example, if $L={\{a,aab,baa}\}$, then $L/a={\{ϵ,ba}\}$.

Let there is CFG $G = (V,\Sigma,S,P)$ where $V$ is set of nonterminals, $\Sigma$ is set of terminals, $S$ is start symbol, $P$ is set of production rules. We assume that $G$ has only form of productions such as $A\rightarrow BC$ and $X\rightarrow a$ since every CFG can be transformed to CNF. Let $V’$ be a empty set. For each $A \in V$, if $A \rightarrow BC$ and $C\rightarrow a$ then add $A’$ in $V’$ and add $A’\rightarrow B$ in $P$. Next, if $A \rightarrow a$ then add $A’\rightarrow \epsilon$ in $P$. For each $A\rightarrow BC$ in $P$, if $C$ in $V’$, then add $A’$ in $V$. Substitute $V’$ with $V$, and remove produtions where exist $A$ where $A \notin V’$.

   

  1. Consider the following two language :

$L_1 = {\{a^nb^{2n}c^m \mid n,m\ge0}\}$

$L_2 = {\{a^nb^mc^{2m} \mid n,m\ge0}\}$

a) Show that each of these languages is context-free by giving grammars for each.

$G(L_1)$:

$S \rightarrow AB \mid \epsilon$

$A \rightarrow aAbb \mid \epsilon$

$B \rightarrow cB \mid \epsilon$

$G(L_2)$:

$S \rightarrow AB \mid \epsilon$

$A \rightarrow Aa \mid \epsilon$

$B \rightarrow bBcc \mid \epsilon$

b) Is $L_1 \cap L_2$ a CFL? Justify your answer.

We can say, $L_1 \cap L_2 = {\{ a^n b^{2n} c^{4m} \mid n, m \geq 0}\}$.

Then by applying pumping lemma to $L_1 \cap L_2$, we can easily notice that $L_1 \cap L_2$ is not CFG.

   

  1. Show that the CFL’s are not closed under the following operations :

a) $min(L)={\{w \mid w}$ is in $L$, but no proper prefix of $w$ is in ${L}\}$.

Step 1 : CFL에 속하는 $L = {\{0^i 1^j 2^k \mid i \leq k}$ or ${j \leq k }\}$에 대해 $min(L) = {\{0^i 1^j 2^k \mid k = min(i,j)}\}$이다. 만약 $k > min(i,j)$ 이라면 $0^i 1^j 2^{min(i,j)}$이라는 proper prefix가 존재하고, 만약 $k < min(i,j)$ 이라면 $L$에 속하지 않는다. 만약 $k = min(i,j)$ 이라면 $L$에도 속하고 $0^i 1^j 2^{min(i,j)-1}$ 이라는 proper prefix가 존재하지 않기 때문에, $min(L) = {\{0^i 1^j 2^k \mid k = min(i,j)}\}$라는 것을 확인 할 수 있다.

Step 2: $min(L) $인 $ {\{0^i 1^j 2^k \mid k = min(i,j)}\}$에 대해 pumping lemma를 적용해보자. n을 펌핑 상수로 선택하고 $z = 0^n 1^n 2^n = uvwxy$ 라고 가정하자. 만약 $vx$가 $2$를 포함하지 않는다면, $uwy$는 $min(L)$에 속하지 않는다. 만약 $vx$가 하나의 $2$를 포함한다면, $ \mid vwx \mid \leq n$ 이기에 $0$을 포함할 수 없다. 이때 $uv^2 wx^2 y$가 적어도 $n+1$개의 $2$, 적어도 $n$개의 $1$, 정확히 $n$개의 $0$을 가지고 있기에 $min(L)$에 포함되지 않는다. 모든 경우에 성립하지 않기 때문에 $min(L)$은 CFL에 속하지 않는다.

Step 3 : CFL에 속하는 L인 ${\{0^i 1^j 2^k \mid i \leq k}$ or ${j \leq k }\}$에 $min$을 적용한 $min(L)$은 CFL에 속하지 않는 모순을 확인했기에, $min$은 CFL에 닫혀있지 않다.

b) $max(L)={\{w \mid w}$ is in $L$ and for no $x$ other than $ϵ$ is $wx$ is ${L}\}$.

Step 1 : CFL에 속하는 $L = {\{0^i 1^j 2^k \mid i \geq k}$ or ${j \geq k }\}$에 대해 $max(L) = {\{0^i 1^j 2^k \mid k = max(i,j)}\}$이다. 만약 $k < max(i,j)$ 이라면 $0^i 1^j 2^{max(i,j)}$이라는 $wx$가 존재하고, 만약 $k > max(i,j)$ 이라면 $L$에 속하지 않는다. 만약 $k = max(i,j)$ 이라면 $L$에도 속하고 $0^i 1^j 2^{max(i,j)+1}$ 이라는 $wx$가 존재하지 않기 때문에, $max(L) = {\{0^i 1^j 2^k \mid k = max(i,j)}\}$라는 것을 확인 할 수 있다.

Step 2: $max(L) $인 $ {\{0^i 1^j 2^k \mid k = max(i,j)}\}$에 대해 pumping lemma를 적용해보자. 3-a의 Step2와 동일한 방식으로 $max(L)$이 CFL에 속하지 않다는 것을 알 수 있다.

Step 3 : CFL에 속하는 L인 ${\{0^i 1^j 2^k \mid i \leq l}$ or ${j \leq k }\}$에 $max$을 적용한 $max(L)$은 CFL에 속하지 않는 모순을 확인했기에, $max$은 CFL에 닫혀있지 않다.

   

  1. The following are the productions of a CNF grammar $G$ :

$S \rightarrow AB\mid BC$

$A \rightarrow BA\mid a$

$B \rightarrow CC\mid b$

$C \rightarrow AB\mid a$

Use the CYK algorithm to determine whether each of the following strings is in $L(G)$ :

a) $ababa$.

$X_{15} = {\{S,A,C}\}$        
$X_{14} = {\{B}\}$ $X_{25} = {\{B}\}$      
$X_{13} = {\{B}\}$ $X_{24} = {\{S,C}\}$ $X_{35} = {\{B}\}$    
$X_{12} = {\{S,C}\}$ $X_{23} = {\{S,A}\}$ $X_{34} = {\{S,C}\}$ $X_{45} = {\{S,A}\}$  
$X_{11} = {\{A,C}\}$ $X_{22} = {\{B}\}$ $X_{33} = {\{A,C}\}$ $X_{44} = {\{B}\}$ $X_{55} = {\{A,C}\}$

$X_{15}$에 $S$가 존재하므로 $ababa$는 $L(G)$에 속함을 알 수 있다.

b) $baaab$.

$X_{15} = {\{S,C}\}$        
$X_{14} = {\{S,A,C}\}$ $X_{25} = {\{S,C}\}$      
$X_{13} = \emptyset$ $X_{24} = {\{S,A,C}\}$ $X_{35} = {\{B}\}$    
$X_{12} = {\{S,A}\}$ $X_{23} = {\{B}\}$ $X_{34} = {\{B}\}$ $X_{45} = {\{S,C}\}$  
$X_{11} = {\{B}\}$ $X_{22} = {\{A,C}\}$ $X_{33} = {\{A,C}\}$ $X_{44} = {\{A,C}\}$ $X_{55} = {\{B}\}$

$X_{15}$에 $S$가 존재하므로 $baaab$는 $L(G)$에 속함을 알 수 있다.