CSc 318 Test 3 Wednesday 1 December 1999.

TEST 3 SUGGESTED ANSWERS

  1. (10 pts) Prove that the grammar below is ambiguous.

    2. S ® AA | BAB

    A ® aa | Sa

    B ® a | abS

    The trees for the following two derivations of aaaa differ.

    SÞ AAÞ aaAÞ aaaa

    SÞ BABÞ aABÞ aaaBÞ aaaa

    S S

    / \ / | \

    A A B A B

    / \ | \ | / \ |

    a a a a a a a a

  2. (17 pts) Find a grammar which is equivalent to the grammar below, which has no useless non-terminals, and which has no useless productions.

    3. S ® aABCE | aBa

    A ® bD | bbE | b | bbA

    B ® aS | bCS | ab

    C ® aS | aC

    D ® aE | bD

    E ® bDD | cE

    First apply Algorithm 3.5.1 to get rid of all non-terminals which never produce terminals.

    Start with P’={B® ab, A® b} N’={A,B}

    Step 1. Add to P’ S® aBa, A® bbA, and add to N’ S.

    Step 2. Add to P’ B® aS, C® aS, and add to N’ C.

    Step 3. Add to P’ B® bCS, C® aC.

    Now we have the grammar

    S ® aBa

    A ® b | bbA

    B ® aS | bCS | ab

    C ® aS | aC

    Now apply Algorithm 3.5.2 to find all symbols that appear in some string

    derivable from S. This give S® aBa, B® aS | BCS | ab, C® aS | aC

  3. (18 pts) Given the two dfa’s M1 = (Q1, S , s1, F1, d 1) and

M2 = (Q2, S , s2, F2, d 2),

    1. Find an e -nfa M such that L(M) = L(M1)*;

      2. M = (Q1È {s}, S , s, F1È {s}, d 1È {(f,e ,s): fÎ F1}È {(s,e ,s1)})

    2. Find an e -nfa M such that L(M) = L(M1) È L(M2); and

      3. M = (Q1È Q2È {s},S , s, F1È F2, d 1È {s, e , s1), (s, e , s2)})

    3. Find an e -nfa G such that L(M) = L(M1) Ç L(M2).

M = (Q1´ Q2, S , (s1,s2), F1´ F2, d 1´ d 2)

where (d 1´ d 2)((q1,q2),a)=( d 1(q1,a),d 2(q2,a))

Note: No credit will be given for providing specific examples. I am asking you to provide the general solution to each problem.
  1. (25 pts) Prove there is no right regular grammar for

    2. A = {an(bcd)n : n³ 1}.

    If a right regular grammar exists, then there exists a dfa for A. Suppose the dfa has k states. Then in accepting the string ak+1(bcd)k+1 we must pass through the same state twice before all of the a’s have been consumed. Thus there is m and p with 1£ m<p£ k+1 and with state m the same as state p. Thus ak+1-(p-m)(bcd)k+1 would also be accepted by the dfa. But the resulting string is not in A. This is a contradiction of the original assumption that we have a right regular grammar for A.

  2. (10 pts) Find a cfg for the language A of question 4.

    3. S ® aSbcd | abcd

  3. (20 pts) Find a regular expression whose language is that of the nfa

M = ({s,1,2,3}, {a,b}, s, {2,3},

{(s,a,1), (s,a,2), (1,b,s), (1,b,3), (2,b,1), (2,b,3), (3,a,3)} )

Let L(X) denote the strings derivable from X.

Then L(s) = aL(1) È aL(2)

L(1) = bL(s) È bL(3)

L(2) = bL(1) È bL(3) È e

L(3) = aL(3) È e

L(3) = a*

L(2) = bL(1) È ba* È e

L(1) = bL(s) È ba*

L(s) = aL(1) È a(bL(1) È ba* È e )

= (a È ab)L(1) È aba* È a

= (a È ab)(bL(s) È ba*) È aba* È a

= (a È ab)bL(s) È (a È ab)(ba*) È aba* È a

Thus L(s) = ( (a È ab)b)*( (a È ab)ba* È aba* È a)