CPS 140 Exam 2 Spring 1999Dr. Rodger1. (20 pts) Answer TRUE or FALSE to the following statements.(a) L={anbmcp| m>n>0,m > p > 0} is a context-free language. (TRUE orFALSE?)(b) L={a2nb3mc3n| n>0,m>0} is a context-free language. (TRUE or FALSE?)(c) Σ = {a, b, c},L={wwR| w ∈ Σ∗,na(w) >nb(w)}is a context-free language.(TRUE or FALSE?)(d) Σ = {a, b, c},L={w|w∈Σ∗,na(w)=4∗nb(w)}is a context-free language.(TRUE or FALSE?)(e) Consider the following state in a DFA used to build an LR(1) parse table. Thenumber of arcs out of this state is 2. (TRUE or FALSE?)S → a BcB → ba BB → baBB → (f) An LL parser is a type of top-down parser. (TRUE or FALSE?)(g) An LR(1) parser must reduce at least one rule before accepting any string, eventhe string . (TRUE or FALSE?)(h) For every CFL L, there exists a DPDA M with no more than 3 states such thatL=L(M).(TRUEorFALSE?)(i) For every regular language, there exists a DPDA M such that L=L(M). (TRUEor FALSE?)(j) The union of a CFL with a regular language is a CFL. (TRUE or FALSE?)2. (7 pt) A nondeterministic PDA (NPDA) M is defined by M=(K,Σ, Γ, ∆, q0,z,F).Name each of the 7 parts in the 7-tuple.(a) K is(b) Σ is(c) Γ is(d) ∆ is(e) q0is(f) z is(g) F is13. (12 pts) Consider L = {anbpcm| 0 <p<2n+m, p > 0,n > 0,m > 0}.Drawthetransition diagram for a nondeterministic pushdown automaton M that accepts L byfinal state. (Remember to identify the start state by an arrow and final states bydouble circles. Format of labels are a, b; cd where a is the symbol on the tape, b is thesymbol on top of the stack that is popped, and cd are pushed onto the stack (with con top of d). Z is on top of the stack when M starts. ).(a) First list 4 strings in L.(b) Now draw the transition diagram.4. (8 points) Consider the following language.Σ={a, b},L={wanwRbm| n is even, n>0,m is odd, m>0,w∈Σ∗}Write a context-free grammar for L. (note that R means the string reversed)5. (3 pts) Consider the following grammar.S → bbCd | bbcC → cC | cThe grammar is LL(k) for what value of k?6. (12 pts) Consider the following grammar (DO NOT change the grammar):S → AbC | dA → aA | C → AcFor this problem you will construct the LL(1) parse table.(a) Calculate FIRST and FOLLOW for the variables in the grammar.FIRST FOLLOWSAC(b) Calculate all entries in the LL(1) Parse Table. If there are multiple rules for anentry, write in all the rules.2a b c d $SAB7. (20 pts) Construct the LR parsing table for the following grammar (DO NOT changethe grammar.) A new start symbol S’ and production have already been added to thegrammar.1) S’ → S2)S→Dc 3) D → dA4) D →  5) A → aS 6) A → a(a) Calculate the FIRST and FOLLOW sets of variables.FIRST FOLLOWSDA(b) Construct the transition diagram of the DFA that models the stack. Number thestates, show marked productions, and identify final states by two circles.(c) Construct the LR parse table that corresponds to the transition diagram drawnin part b. (Note: all the rows and columns given may not be needed. If there aremultiple items for an entry, put both.)301234567891011128. (10 pts) Pumping Lemma for CFL’s Let L be any infinite CFL. Then there is aconstant m depending only on L, such that for every string w in L,with|w|≥m,wemay partition w = uvxyz such that:|vxy|≤m, (limit on size of substring)|vy|≥1, (v and y not both empty)For all i ≥ 0, uvixyiz ∈LProve that L={anbpcq|n>p>q>0}is not a context-free language.You only have to fill in the parts below. Assume L is a context-free language.(a) Choose w =(b) Prove the case when v = bt1and y = bt2(both are strings of b’s)(c) Prove the case when v = bt1and y = ct249. (8 pt) Suffix(L)={w ∈ Σ∗| x = yw, for some x ∈ L, y ∈ Σ∗} (the set of suffixes of L).For example, if L={anbn|n>0}thenSuffix(L) = {aaabbb, aabbb, abbb, bbb, bb, b, aabbbbb, bbbbbb, ...}Prove that if L is a CFL, then Suffix(L) is also a context-free language. (Hint: L hasan NPDA M=(K,Σ, Γ, ∆, q0, z, F), construct NPDA M’ to represent Suffix(L))•