-
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^n b^{2n} c^m \mid n, m \geq 0}\}$
$L_2 = {\{ a^n b^m c^{2m} \mid n, m \geq 0}\}$
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 (See Homework 9).
- 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에 닫혀있지 않다.
-
Give algorithm to decide the following :
a) Is $L(G)$ finite, for a given CFG $G$?
First, eliminate $\epsilon$-, unit, useless productions and make clean grammar. Second, draw a directed graph whose nodes are variables of the given grammar. If there exist circle, then $L(G)$ is infinite otherwise finite.
b) Does $L(G)$ contain at least 100 strings, for a given CFG $G$?
First, apply (a).
Second, if $L(G)$ is infinite, return true.
Third, if not, enumeration all possible derivations from start variable. if there are at least 100 different strings, return true, otherwise, return false.
- 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)$에 속함을 알 수 있다.