Context Free Languages (CFLs)


> 

> ## Pumping lemma (for CFLs)

![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F4a4dad99-89f3-4287-80bc-514e3e420e58%2FUntitled.png?table=block&id=5ef714a7-694d-4bec-a909-39b2d3466cae&cache=v2)
> 

> <details><summary>
> 
> **There is repeated variable**</summary>

> Suppose that L is a CFL and G is a grammar in CNF such that L(G) = L\{λ}
> 1. Every parse tree T for G is a binary tree since every production is of the form A → BC or A → σ
> 2. If height(T) = k, then T has at most 2k−1 leaves (proof by induction) and, thus, yield(T) is a string of length ≤ 2^{k-1}
> 3. Suppose that G has k variables. This implies that if yield(T) is “long” (length > 2k−1), then height(T) ≥ k + 1
>> - there is a “long” path from the root (S) to some leaf
>> - this path has more than or equal to k + 1 variables and, by the pigeon hole principle, **at least one variable must be repeated**
> </details>
> 
> 

> 



### A**t least one variable must be repeated**
> **Find repeated variable A**
>> Suppose that the long string is z and the repeated variable is A.
>> Then, S ∗ =⇒uAy ∗ =⇒uvAxy ∗ =⇒uvwxy = z
>> This means that** A **∗ =⇒vAx ∗ =⇒vvAxx ∗ =⇒v3Ax3 ∗ =⇒··· ∗ =⇒***viAxi*** ∗ =⇒···
>> $$then \,\, A →^* v^iAx^i$$

> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F6e87cce0-557e-4e23-afc0-436d5d340eb2%2FUntitled.png?table=block&id=d437eb72-7d0a-4d39-9093-adf3302d01b5&cache=v2)



> ### Proof Procedure

> <details><summary>
> 
> example</summary>

> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F28d4a6da-83c8-4a6b-8bb2-f730323154ab%2FUntitled.png?table=block&id=e631e1a8-ca6e-40f4-bece-4d8eb47ad2af&cache=v2)
> 
> </details>
> 

Let L be a CFL. Then, there exists a positive integer n such that if z is any string in L with |z|≥ n, then we can write z = uvwxy, where
1. |vwx|≤ n: That is the middle part is not too long
2. vx 6= λ: Since v and x are the pieces to be pumped, this condition says at least one of the strings we pump must not be empty
3. ∀i ≥ 0, uviwxiy ∈ L when in all kind of vwx cases 
<details><summary>

Once again, think of it as a game</summary>

1. Language unabitablily has n
2. 2You choose z ∈ L such that |z|≥ n and **present it by n **
3. then it has u,v,w,x and y that satisfy the properties 
4. You choose contradiction i ≥ 0 such that uviwxiy / ∈ L
</details>

### we use contradiction of `math: uv^iwx^iy ∈ L`



# Closure properties
> ### Closed
> - union
> - catenation
> - Kleene star
> - homomorphisms
> - inverse homomorphisms
> - reversal 
> - substitution
> 

> ### Not Closed
> - intersection - by example
>> L intersection R is CFL
> <details><summary>
> 
> proof</summary>

> Let P be a PDA that accepts L by ﬁnal state and A be a DFA that accepts R. The PDA recognizing L∩R simulates P and R simultaneously and accepts if both P and A accept the input.
> 1. Like in the “Cartesian product” construction, states of the new machine are pairs of states, where one element of the pair corresponds to the state of P and the other corresponds to the state of A
> 2. Whenever an input symbol is read, both P and A are simulated; if P needs to make a λ move, then A remains stationary
> </details>
> 
> - complementationGiven a CFL L, its complement L is** not context**-free
> <details><summary>
> 
> proof</summary>

> We have two reasons:
> 1. If CFLs are closed under complement, then by De Morgan’s law and by the fact that CFLs are closed under union, CFLs would be closed under intersection. But, we know it’s not true.
> 2. L = {x | x not of the form ww} is a CFL. But L = {ww | w ∈{a,b}∗} is not a CFL. • If L were a CFL, then L0 = L∩a∗b∗a∗b∗ = {aibjaibj | i,j ≥ 0} would be a CFL. But L0 is not a CFL! (Notice a∗b∗a∗b∗ is regular.)
> </details>
> 
> - differenceIf L1 and L2 are CFLs, then L1 \L2 is not a CFL.
> <details><summary>
> 
> proof</summary>

> CFLs are not closed under complement, and complement is a special case of set diﬀerence. (L = Σ∗\L)
> </details>
> 



<details><summary>

**At proving, Consider a PDA A for L. We make three copy of A, call Aeven, Aodd - Method and substitution used a lot**</summary>

> non-CFL: closed under reversal - reverse the RHS of all production rules
> if some type of language set(ex. RL, CFL) they are closed under reversal and complementation → non-language also closed under them

</details>

> If L is a CFL and R is a regular language, then L\R is a CFL - Proof: L\R = L∩R.




# Substitutions
### new operation denoted by s(w) 
<details><summary>

we replace each symbol in the strings of one language by an entire language. (a generalization of the homomorphism)</summary>

- S(σ) is set of word
- s(w) is catanation of s(alphabet of w)
- s(L) is union of s(string of language)
</details>




## Substitution Theorem - closed property to CFL
**Substitution theorem**: Let L be a CFL over Σ and s(·) be a substitution such that s(a) is a CFL ∀a ∈ Σ. Then, s(L) is a CFL.
<details><summary>

**Proof**: From s(·), we replace each terminal a by the start symbol of a CFG for language s(a).</summary>

Let G = (V,T,S,P) be a CFG for L and Ga = (Va,Ta,Sa,Pa), for each s(a).We construct G0 = (V 0,T0,S0,P0) for s(L), where
1. V 0 = ([ a∈Σ Va)∪V
2. T0 = ([ a∈Σ Ta)
3. P0 = ([ a∈Σ Pa) plus the productions of P but each terminal a occurrence in the rule is replaced by Sa
</details>




### Non-DCFL
L = {aibi}∪{aib2i} for n ≥ 0 is context-free but not deterministic context-free.
<details><summary>

Proof: L has a CFG:</summary>

S → S1 | S2 S1 → aS1b | λ S2 → aS2bb | λ
and, thus, is context-free.Non-DCFLWe show that there is no DPDA recognizing L. For contradiction, assume that there is a DPDA A for L; namely, L(A) = {aibi}∪{aib2i}.
Now we construct a PDA recognizing aibici using A, which should be impossible.
![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F54678103-2453-450e-96a2-b5763582eedd%2FUntitled.png?table=block&id=ec780d7a-bdcc-4307-9b17-ba2655be3457&cache=v2)
Now we construct a PDA recognizing L∪aibici using A.
![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Ffe45f57e-2ef7-4481-9848-4f9c7ad0a697%2FUntitled.png?table=block&id=23e04da9-f9b2-4edf-9b45-8df4fb324c0b&cache=v2)
C is a PDA recognizing L∪aibici—contradiction. Therefore, L = {aibi}∪{aib2i} is not a DCFL.
</details>




###  Decision problem
<details><summary>

**We can test membership in polynomial time**</summary>

![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F4f109634-0737-419b-af84-544ca8c9b92f%2FUntitled.png?table=block&id=e46ca4a1-7b43-4a7d-9def-533dc32362b3&cache=v2)


![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F1d87e2a5-171d-482b-b470-224f72b0dfe2%2FUntitled.png?table=block&id=2dccdd67-478c-46f3-ae39-45ce6a272099&cache=v2)
</details>

<details><summary>

A CFL is deﬁned by a CFG or is accepted by a PDA.</summary>

1. Size of grammar is an upper bound on the number of variables, the number of productions, and the length of each production
2. Size of a PDA is an upper bound on the number of states, the number of transitions, the number of symbols pushed into the stack in any step and so on
</details>




# CYK Algorithm
<details><summary>

**Testing membership : Decide whether or not a string w in a CFL L.**</summary>

The core of CYK algorithm: Given a CFG G = (V,T,S,P) in CNF and an input string w = a1a2···an, Construct a table, where each cell Xij contains all variables A ∈ V such that A ∗ =⇒aiai+1···aj.
A naive way to test membership takes exponential time in the size of |w|. We discuss an eﬃcient technique based on the idea of dynamic programming: CYK algorithm: 
</details>

![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fd7b7d77a-0d86-40ef-833b-1e380d6b969f%2FUntitled.png?table=block&id=6002528d-38f9-4e88-bab9-36445bc8ff05&cache=v2)
> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Feaca4236-e0c6-424c-af29-1f669efa24fa%2FUntitled.png?table=block&id=c52f86bc-ba8a-4945-9126-51e49f7ec1d8&cache=v2)

> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F08870253-4344-4011-a085-36babd6bbb05%2FUntitled.png?table=block&id=0938a9de-ce90-413c-be1a-c0f4563ed3bf&cache=v2)

**Find X_45 which has double varible(x_44x_55 catenation) CNF form in righht side - if null →cannot catenation**



