- 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$
- 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$
- 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$
- 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로는 증명할 수 없다.
- 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’$.
- 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.
- 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에 닫혀있지 않다.
- 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)$에 속함을 알 수 있다.