Context-Free Grammar Cleanup and CNF Conversion

B) DISPOSAL OF SYMBOLS NOT ACCESSIBLE: 1) Initialize N '= (s), =, P' = 2) Repeat: for A € N ', if A -> is a production of P, then: 2.1) Introduce A -> w in P '2.2) For all non-terminal B dw, enter B in N' 2.3) For every terminal dw, to introduce q + no rules can be added to P '.






C) ELIMINATION OF RULES - Epsylon: G = (N, P, S) such that € L (G) S -> (this does not delete) rest d epsylon rules can be eliminated: Symbol void: A € N is voidable if A = ^*> / / 1) All d symbols of a grammar voidable () is calcla: 1.1) Initialize all nonterminals A such q A -> € P 1.2) Repeat: add to cough that the nonterminals B q B -> w € P dw and all markings are in until they can not add q + nonterminal to2) We modified the rules d P as follows: Let B -> x ₁ x ₂ ... X _n € P, we introduce in P 'all of the following productions: B -> and ₁ and ₂ ... And _n such q _i = x _i if x _i is not voidable, x _i or x _i SI is voidable, x _i can be for all i • NOTE: If € L (G) at the end add S ->






D) DISPOSAL UNIT D RULES: (A (non-terminal) - B (not terminal)): for each A € N, unit (A) = (B € N / A =*> B using only unitary rules). We calculate P ': 1) Initialize P' = P2) For each A € N, obtain unit (A) 3) For every A € N such unit q (A) other than (A): B € tpdp unit for (A): for all B -> w € P add A -> wa P '4) Eliminate unit rules of P'






• 1st DISPOSAL epsylon apply, then unit, then A) and B)
3.6 Chomsky normal form: we say q is a grammar in Chomsky normal form d where d all the way rules are: A -> or A -> BC • How to pass a clean arbitrary grammar G (with no rules or epsylon unitary rules useless symbols or symbols or inaccessible) to another G '? -> For each grammar rule is d (epsilon if part of S, we remove and work without it, in the end we put): A -> w as q | w |> = 11a) | w | = 1 (w has only one symbol: w is necessarily a terminal (this cleans pq), the rule is left, already in 1b FN) | w |> 1, A -> x _1, x ₂ ..., x _n1b.1) where x _i is a nonterminal, not touched 1B.2) where x _i is the terminal, change to a non-terminal and add the rule -> 2) binarized the rule: A -> B ₁ D _1, D ₁ - B ₂ D ₂ ...... D _n-2 - B _n-1 B _n3) At the end if € L (G) add Rule S ->.