- 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$
- 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$
- 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$
- 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들을 가질 수 있다는 사실을 확인 할 수 있다.
- 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.
- 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로는 증명할 수 없다.