CSCI435-Assignment 4 Solved  

Q1. [20] For a given language L = {anb2n | n ³ 0 is even}.

(1)  [8] Give a CFG that accepts L.

S - aaSbbbb | ε

(2)  [6] Show the sequence of derivations for the acceptance of aaaabbbbbbbb by G in (1).

S - aaSbbbb

   - aaaaSbbbbbbbb

   - aaaabbbbbbbb

(3)  [6] Draw a derivation tree for aaaabbbbbbbb.

 

Q2. [30] Construct a CFG for the following languages where n, m, k ³ 0.

(1)  [10] L1 = { anbn | n is a multiple of 3 }

(a3)x(b3)x 

(aaa)x(bbb)x

S - aaaSbbb | ε

(2)  [10] L2= { anbmck | k = n+m }

= Anbmck

= anbmcn+m

= anbmcncm

= ((ancn)/A) ((bmcm)/b)

S - AB

A - aAc | ε

B - bBc | ε

(3)  [10] L3 = { anbm | n = m –1 }

N = m – 1 

N + 1 = m 

= Anbn+1 

= (anbn)/x * b

S - xb 

X - axb | ε

(4)  [10, optional] L4 = { anbmck | n=m or m £ k }

N = m or m <= l 

(anbn/u)(ck/v)     or       (an/x) (bmckck/y)

S - UV | XY

U - aUb | ε

V - cV | ε

X - aX | ε

Y - bYc | c | bAc | ε

A - cA | c

Q3. [10] Give the language L that is generated by the given grammar, in a formal expression.

                                             S ® aaSbb | SS | l.         

               e.g.) L = { w Î {a, b}* | na(w) = 2nb(w) }

 

L = (aa)* (bb)* 

Because a and b are in pairs

Q4. [10] Find an s-grammar for L = {anb2n | n ³ 2}.

1 – a and 2 – b’s 

X, Y, Z 

Start at S 

AaSbbbb | ε l

 

S - aS1 

S1 - aXYZ

X - bY | aXYZ

Y - b

Z - b 

 

Q5. [20] For a grammar G with the productions where G = ( {S, A, B}, {a, b}, S, P ) with productions

                                             S ® AB | bbbB,              A ® b | Ab,       B ® a..

(1)  [8] Show that the grammar G is ambiguous.

 

Because there are two separate trees, it shows that it is ambiguous 

(2)  [6] Give language L that is generated by G, L = L(G), in a formal expression (including a regular expression).

 S - AB | bbbB 

A - b | Ab   = bAb = b+ (at least one b)

B - a..

AB = b_a..

S - AB | bbba..

S - b+a.. | bbba..

(b++bbb)a..

(3)  [6] Can you construct an unambiguous grammar that is equivalent to G? Otherwise, show that G is inherently ambiguous.

If we substitute “A” in “S” it equals 

S - b+ | bbbB

B- a..

Thus being unambiguous because removing “A,” the ambiguous is removed. 

 

Q6. [35] In the given grammar G, generate the simplified equivalent grammar by eliminating the following productions through (1) – (3).

               G = ( {S, A, B, C}, {a, b},  S, P ) with productions

               S ®bAA | bB,     A ® aA | aaC ,   B ® bbB | l,      C ® A

(1)  [10] Eliminate the l-productions 

S - bAA | bB | b

A -  aA | aaC 

B -  bbB | bb

C - A

(2)  [10] Eliminate the Unit-productions from (1)

S - bAA | bB | b

A - aA | aaC 

B - bbB | bb

(3)  [10] Eliminate the useless productions (2), so that give the simplified equivalent grammar.

S - bB | b

B - bbB | bb

(4)  [5] Give the language L that is generated by this grammar, L = L(G), in a formal expression (including a regular expression).

(bb)*b

Containing b’s of odd length 

 

Q7. [15] Convert the given grammar into Chomsky Normal Form (CNF).

               S ® AB | aB,      A ® abb | l ,      B ® bbA 

 

Hint: Eliminate the l-productions and/or any unit-production prior to their conversion into CNF.

 

Removing λ productions

S - AB | aB | B
A - abb
B - bbA | bb

Removing unit productions

S - AB | aB | bbA | bb
A - abb
B - bbA | bb

Removing mixed rules

S - AB | WB | VVA | VV
A - WVV
B - VVA | VV
W - a
V - b

Change to final CNF

S - AB | WB | CA | VV
A - WC
B - CA | VV
W - a
V - b
C - VV

 

Q8. [10] Convert the given grammar into Greibach normal form.

                              S ® aSb | ab | bb

S - aSTb

S - aTb

S - bTb

Tb - b

 

= S - aSTb | aTb | bTb 

      Tb - b