Mathematical Foundation of Computer Science

DHARM 284 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE B a S a a {A,qf} Fig. 11.8 11.5CONTEXT FREE GRAMMARS (CFG)/(TYPE-2 GRAMMAR ...

DHARM NON-REGULAR GRAMMARS 285 All strings formed by two different substrings One substring starting with a’s followed by equal ...

DHARM 286 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE S ⇒ a B ⇒ a b S ⇒ a b b A ⇒ a b b a S ⇒ a b b a a B ⇒ a b b a a b S ⇒ a b ...

DHARM NON-REGULAR GRAMMARS 287 for the strings that have equal number of a’s and c’s and in between there are multiple of b’s so ...

DHARM 288 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE S S + ( ) SS a ( S ) SSH aa Fig. 11.10 Hence, S ⇒N (a + (a H a)) is the yi ...

DHARM NON-REGULAR GRAMMARS 289 Thus, we may find more derivation sequences and consequently more derivation trees for a single t ...

DHARM 290 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE There exists another right most derivation sequence for the string ‘a + a ...

DHARM NON-REGULAR GRAMMARS 291 I. lm derivation sequence S ⇒ T + S ⇒ F + S ⇒ a + S ⇒ a + T ⇒ a + F H T ⇒ a + a H T ⇒ a + a H F ⇒ ...

DHARM 292 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Both shows unique derivation tree. Hence G may be unambiguous. l Test with ...

DHARM NON-REGULAR GRAMMARS 293 l For string ∈(∈(∈)): S ⇒ S(S) ⇒ S(S(S)) ⇒ S(S(∈)) ⇒ S(∈(∈)) ⇒∈(∈(∈)) Here we again reach to a un ...

DHARM 294 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE input symbol is not used, and the tape head is not advanced after the move ...

DHARM NON-REGULAR GRAMMARS 295 abb... M Z 0 : : H p Finite Control ... x g A Fig. 11.20(b) Language of a PDA Finally, we define ...

DHARM 296 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE •δ (q 1 , b, X) → {(q 2 , ∈)} [If next input alphabet is b then pop the st ...

DHARM NON-REGULAR GRAMMARS 297 [While other moves like δ (q 2 , a, Z 0 ) → Ø and δ (q 2 , b, Z 0 ) → Ø where state Ø signifies t ...

DHARM 298 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE II. (q 1 , b b a a, AAZ 0 )  (q 1 , b a a, BAAZ 0 )  {(q 1 , a a, BBAA ...

DHARM NON-REGULAR GRAMMARS 299 Lemma 11.1 Let G = (VN, VT, S, P) be a CFG that allows null production/s (A → ∈) then the languag ...

DHARM 300 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE l S → ∈ is a nullable production (S is nullable), remove it from G, i.e., ...

DHARM NON-REGULAR GRAMMARS 301 l Third iteration, Old V = {B, A, S} and new V = {B, A, S} with non existence of other nullable. ...

DHARM 302 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE (+) S → a X Y [S → a X Y Z when Z → ∈ is removed] also production (+) Z → ...

DHARM NON-REGULAR GRAMMARS 303 Example 11.21. Similar to previous example, let language L is expressed by the regular ex- pressi ...