# Theory of computing - Hw6
#### Author : 資管一 B12705064 趙子佾
---
### 1. (Exercise 2.2; 10 points)
(a) Use the languages $A = \{a^nb^nc^m\ |\ m, n ≥ 0\}$ and $B = \{a^mb^nc^n\ |\ m, n ≥ 0\}$, together with the fact that $\{a^nb^nc^n\ |\ m, n ≥ 0\}$ is not context free, to show that the class of context-free languages is not closed under intersection.
> to rewrite A and B into $A = \{a^ib^jc^k\ |\ (i=j)\wedge (i,j,k ≥ 0)\}$ and $B = \{a^ib^jc^k\ |\ (j=k)\wedge (i,j,k ≥ 0)\}$
> Since $A\cap B = \{a^ib^jc^k\ |\ (i=j)\wedge (j=k)\wedge (i,j,k ≥ 0)\}$, that is $A\cap B = \{a^ib^ic^i\ |\ i ≥ 0)\}$, which is not context-free.
> $\rightarrow$ the class of context-free languages is not closed under intersection.

(b) Use the preceding part and DeMorgan’s law to show that the class of context-free languages is not closed under complementation
> Suppose the class of context-free languages in closed under complementation.
> With the proceding step of DeMorgan's law
> A and B are context-free
> $\bar A$ and $\bar B$ are context-free
> $\bar A \cup \bar B$ is context-free
> $\overline {\bar A \cup \bar B}$ is context-free
> $A \cap B$ is context-free $\rightarrow$ **False**
Since we have this contradiction, the class of context-free languages is not closed under complementation.
### 2. (Exercise 2.5; 20 points) Give informal descriptions and state diagrams of pushdown automata for the following languages. In all parts the alphabet Σ is {0, 1}.
(a) \{w | the length of w is a multiple of 3\}
> 

(b) \{w | w is a palindrome, that is, $w = w^R$\}
> 

### 3. (Exercise 2.12; 10 points) Convert the following CFG to an equivalent PDA, using the procedure given in Theorem 2.20.
$E\rightarrow E+T\ |\ T$
$T\rightarrow T\times F\ |\ F$
$F\rightarrow (\ E\ )\ |\ a$
> 
> 
> 
> 
> 

### 4. (Problem 2.39; 20 points) Let G = (V, Σ, R,⟨STMT⟩) be the following grammar.
⟨STMT⟩ → ⟨ASSIGN⟩ | ⟨IF-THEN⟩ | ⟨IF-THEN-ELSE⟩
⟨IF-THEN⟩ → if condition then ⟨STMT⟩
⟨IF-THEN-ELSE⟩ → if condition then ⟨STMT⟩ else ⟨STMT⟩
⟨ASSIG⟩ → a := 1
Σ = \{if, condition, then, else, a := 1\}
V = {⟨STMT⟩,⟨IF-THEN⟩,⟨IF-THEN-ELSE⟩,⟨ASSIG⟩}
G is a natural-looking grammar for a fragment of a programming language, but G is
ambiguous.
(a) Show that G is ambiguous.
> let's talk about this sentence $\rightarrow$ if condition then if condition then a:=1 else a:=1
> We can find two deviation to this sentence
> deviation 1:
> \<STMT\> $\rightarrow$
> \<IF-THEN\> $\rightarrow$
> if condition then \<STMT\> $\rightarrow$
> if condition then \<IF-THEN-ELSE\> $\rightarrow$
> if condition then if condition then \<STMT\> else \<STMT\> $\rightarrow$
> if condition then if condition then \<ASSIGN\> else \<ASSIGN\> $\rightarrow$
> if condition then if condition then a:=1 else a:=1
> deviation 2:
> \<STMT\> $\rightarrow$
> \<IF-THEN-ELSE\> $\rightarrow$
> if condition then \<STMT\> else \<STMT\>$\rightarrow$
> if condition then \<IF-THEN\> else \<STMT\> $\rightarrow$
> if condition then if condition then \<STMT\> else \<STMT\> $\rightarrow$
> if condition then if condition then \<ASSIGN\> else \<ASSIGN\> $\rightarrow$
> if condition then if condition then a:=1 else a:=1
>> Since we have two deviation from this sentence, G is ambiguous.

(b) Give a new unambiguous grammar for the same language.
> \begin{align}
> &⟨STMT⟩ → ⟨ASSIGN⟩\ |\ ⟨IF-THEN⟩\\
&⟨IF-THEN⟩ → \text{if condition then}\ ⟨STMT⟩\ |\ ⟨IF-THEN-ELSE⟩\\
&⟨IF-THEN-ELSE⟩ → \text{if condition then}\ ⟨IF-THEN-ELSE⟩ \ \text{else}\ ⟨STMT⟩\ |\ \text{if condition then} ⟨ASSIGN⟩ \text{else} ⟨STMT⟩\\
&⟨ASSIGN⟩ → a := 1
> \end{align}

### 5. (Problem 2.32; 20 points) Let A/B = \{w | wx ∈ A for some x ∈ B\}. Show that, if A is context free and B is regular, then A/B is context free.
> First, we can build a PDA $M_A$ recognizing A and DFA $M_B$ recognizing B.
> We suppose A/B is context-free, then we can construct a PDA $M_{A/B}$
> $M_{A/B}$ works in two stages. In first stages, $M_{A/B}$ works just like $M_A$, but use $\epsilon$ branch to $M_B$ for every state in $M_{A/B}$.
> This is used to suppose reaching w, going to x, which is regular language.
> And when in second stages, these DFA will identify all the input and to the accept state.
> Since we can build a PDA of $M_{A/B}$, A/B is context-free.
### 6. (10 points) Prove (using the pumping lemma) that $\{a^mb^nc^{m×n}\ |\ m, n ≥ 1\}$ is not context free.
> Attempt to pumping $a^pb^2c^{2p}$, p is pumping length
> 
> Method 1&2 fails because they won't in this grammar if $i\neq 1\cup j\neq 1$
> Method 3 fails because no matter x=bb or x=a...bb or x=bbc..., it also won't obey the grammar.
> Since we can't find any slice method to the pumping lemma, this language is not context-free.

### 7. (Problem 2.57; 10 points) Let A = $\{wtw^R\ |\ w, t ∈ \{0, 1\}^∗\ and\ |w| = |t|\}.$ Prove that A is not context free.
> Attempt to pumping $0^p1^p0^p$, p is pumping length
> 
> Method 1 fails because $|w|\neq |t|$ and there is no palindrome anymore when $i\neq 1$
> Although method 2 can obey the $wtw^R$ form, but violate the rule "$|w|\neq |t|$" when $i\neq 1$
> Method 3 fails because it violate the rule "$wtw^R$" when $i\neq 1$
> Since we can't find any $uv^ixy^iz$ form to satisfy this language, this language is not context-free.