Mathematical Foundation of Computer Science

DHARM 304 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE l Since, definition of production A is non terminative so it is a useless ...

DHARM NON-REGULAR GRAMMARS 305 Example 11.23. Consider the grammar S → S + T | T T → T H F | F F → (S) | a Remove unit productio ...

DHARM 306 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE We see that, the new grammar still has some new unit productions. Unit pro ...

DHARM NON-REGULAR GRAMMARS 307 Remove unit production S → A l while, S ⇒ A and A derives terminal then we say that S generates ...

DHARM 308 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE begin Old V = ∅; New V = {A ∈ VN / A → α is in P and α ∈ VT*) While (old V ...

DHARM NON-REGULAR GRAMMARS 309 C → abCa | aDb D → bD | aC Sol. Since grammar G uses the non terminals {S, A, B, C, D} and termin ...

DHARM 310 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE A → aB [then replace a by Xa] s.t. (+) Xa → a So, A → XaB, and Xa → a are ...

DHARM NON-REGULAR GRAMMARS 311 Now we have the remaining non CNF form productions are (i)A → XbAA and (ii)B → XaBB In (i) we put ...

DHARM 312 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE (–) A → A a | b (+) A → b | b A′ (+) A′ → a | a A′ Or, in general (–) A → ...

DHARM NON-REGULAR GRAMMARS 313 Sol. Step 1. Since the grammar is in simplified form also in and CNF so directly switch to next s ...

DHARM 314 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE A 3 → A 3 A 1 A 3 A 2 and further A 2 is replaced through b[∴ A 2 → b] so ...

DHARM NON-REGULAR GRAMMARS 315 and C → bA 3 A 2 A 1 A 3 A 3 A 2 C | aA 2 A 1 A 3 A 3 A 2 C | cA 1 A 3 A 3 A 2 C | bA 3 A 2 CA 1 ...

DHARM 316 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Assume length of largest path is k(k >1) then the sub trees TB and TC h ...

DHARM NON-REGULAR GRAMMARS 317 u vw xy z S X Y A A Fig. 11.26 String w is the yield of sub tree rooted at lower A. v and x are t ...

DHARM 318 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE A S w u y A S A y x x x w v v v u A A (d)(e) Fig. 11.27 (Continued) In the ...

DHARM NON-REGULAR GRAMMARS 319 11.13 Properties of Context Free Languages....................................................... ...

DHARM 320 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE l Assume a new start symbol S. l The set P of productions contains all the ...

DHARM NON-REGULAR GRAMMARS 321 So, G′ includes following tuples, l Set of non terminals i.e., VN ∪ S′, l Set of terminals i.e., ...

DHARM 322 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE 11.14 DECISION PROBLEMS (DP) OF CONTEXT FREE LANGUAGES In the previous cha ...

DHARM NON-REGULAR GRAMMARS 323 A B S Self loop on A Fig. 11.30 The directed graph of A → AB has self loop on symbol A so there e ...