Formal Language and Automata Homework 9 Answer

       

  1. Begin with the grammar :

$S \rightarrow ASB \mid \epsilon$

$A \rightarrow aAS \mid a$

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

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 Exercise 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$

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 Exercise 1 for the following grammar:

$S \rightarrow AAA \mid B$

$A \rightarrow aA \mid B$

$B \rightarrow \epsilon$

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로는 증명할 수 없다.