CFG Removing ambiguity


<details><summary>

**No algorithgm - make higher binding strength terminal to lower part of tree**</summary>

1. no grouping of sequences - make precedence grouping symbol
2. Since there is no precedence - solve by binding strength**factor** : cannot be broken apart by an adjacent**term : **cannot be broken by small binding strength**expressions : **all**Identifier : **operand for operation like terminal
> ```typeE -> T|E + T # != T + ET -> F|T * FF -> I | (E)I -> ...```
</details>

- various left / right most derivation imply various parse tree
> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fe09fd7f5-aad8-4e59-8d4a-447af342de59%2FUntitled.png?table=block&id=f17afcbb-e382-471c-970b-b5643937fe45&cache=v2)
> → left, right distinct derivation go along





# Simplification**s**
1. Remove λ-productions
2. Remove unit productions
3. Remove redundant symbols - unreachable, non-terminating
<details><summary>

We only** consider CFLs that do not have the empty string λ **since it makes easy to understand many claims and proofs. **This does not lose generality**</summary>

- just by adding new start symbol method `math: S_0 \rightarrow S \, | \, \lambda`
- To any nontrivial results, there is method of obtaining  G' `math: L(G') = L(G) \, \backslash \, {\lambda}`
</details>




## Substitution rule
$$A → x_1Bx_2\\B → y_1 \,|\,y_2 \,|\, \dots \,|\, y_n\\A → x_1y_1x_2 \,|\,x_1y_2x_2 \,|\, \dots \,|\, x_1y_nx_2$$
<details><summary>

G' constructed by replacing variable A,B with A' in G has same CFL - by first and second line, we can construct final line (y can be sentential form)</summary>

### Proof - easy
- if `math: w \in L(G),` then `math: w \in L(G')`
1. by assumption, `math: S →^*_G w`
2. if this derivation does not use production `math: A → x_1Bx_2`, it is immediate that `math: S \rightarrow^*_{G'} w`
3. if it does, at G, `math: S →^*_G u_1Au_2 →_G u_1x_1Bx_2u_2 →_G u_1x_1y_jx_2u_2`
4. if it does, at G, `math: S →^*_{G'} u_1Au_2 →_{G'} u_1x_1y_jx_2u_2`
5. we reach the same sentential form with G and G'
6. by induction of rewriting steps, we have *then* part
- if `math: w \in L(G'),` then `math: w \in L(G)` case also has same sentential form
</details>




## 2. Removing redundant symbols
All terminals in T are always terminating
4. **non-terminating **: unable to derive any terminal strings
5. **unreachable** : does not appear in any sentential form
**Redundant** : non-terminating remove by substitution and unreachable removed directly


### Algorithms
- detect terminating symbols
A in V has a production that consists solely of terminating symbols then A is terminating - start from terminal and lambda
- detect reachable symbols (terminal is symbol either)
if A is reachable then all symbols in A are reachable - start from S



## 3. Removing λ-productions
λ-**free** : G property if G has no null production
λ-**variable** : `math: A →^+ λ`
<details><summary>

**If no λ-productions → length *****monotonically *****increasing**</summary>

1. Find set `math: V_N` of all λ-variables of G(a) Find all λ-productions and put that variable into `math: V_N`(b) Foll all production B → `math: A_1A_2 \dots A_n`, where `math: A_1A_2 \dots A_n \in V_N` then put B into `math: V_N`
2. For each element A of `math: V_N` 
> $$A \rightarrow x_1x_2\dotsx x_m\,\, for \,\,m≥1$$
> from variable which has λ-production where `math: x_i \in V \cup T`, we add new production by replacing  λ-variable in all possible combinations from that production symbol  (combination of variable which can be λ)
3. Remove all λ-productions
4. Then finally remove all non-terminating symbols
</details>

> λ-productions = empty production = null production
> production means of 'or' part, not all of right side of p in P




## 4. Removing unit productions
**Unit production **: A → B by substitution rule


**Claim**
>  Given a CFG G = (V,T,P,S) without λ-productions, there is an equivalent CFG G' = (V 0,T,S,P') that does not have any unit productions
<details><summary>

M**ethod**</summary>

 If a unit production is A → A, then, we can remove it from P immediately without aﬀecting L(G).
 In case of A → B, for each variable A, we ﬁnd all variables such that A* ⇒ B using a **dependency graph** for variables in V based on P. (A*⇒B holds when there is a path from A to B in the graph.)
1. Put into P' all non-unit productions of P
**And then remove unreachable**
2. For all A and B of A*⇒B**(**has transitive property**)**, we add to P' A → y1 | y2 |···| yn, where B → y1 | y2 |···| yn is the set of all rules in P' with B on the left **from not dependency which has not B**
</details>


- in this picture remove B
- final is new + right down - unit production
![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fa75621c9-b83c-4c05-aeee-796759f4b63b%2FUntitled.png?table=block&id=387588f2-2f45-41e9-bed3-ea0f9d81f2ce&cache=v2)


**So  by these 4 Simplification, given a CFG, there is an equivalent CFG that does not have any redundant symbols, λ-productions or unit productions.**










