CSc 318 Test 2 Wednesday 3 November 1999

SUGGESTED ANSWERS.

  1. (15 pts) Let A={aab, ba}, B={b, bb}, C={baba, ab, a} be languages over S ={a,b}. Find
  1. (AB-BC)={aab,ba}{b,bb}-{b,bb}{baba,ab,a}

    2. ={aabb,aabbb,bab,babb}-{bbaba,bab,ba,bbbaba,bbab,bba}

    ={aabb,aabbb,babb}

  2. AB2 = {aab,ba}{b,bb}{b,bb}

    3. ={aab,ba}{bb,bbb,bbbb}

    ={aabbb,aabbbb,aabbbbb,babb,babbb,babbbb}

  3. (BC)R = ({b,bb}{baba,ab,a}) R

= {bbaba,bab,ba,bbbaba,bbab,bba} R

={ababb,bab,ab,ababbb,babb,abb}
  1. (15 pts) Recursively define the language B over S ={a,b} by
  1. e Î B
  2. for wÎ B, awbÎ B.
  1. Use this recursive definition to formally prove that |w| is even for all

    2. wÎ B.

    Use induction on the length of w:

    Base case: |w|=0. This is the case when w=e , and it is clearly true.

    Inductive case: Assume that for all w with |w|£ n, |w| is even, and suppose |w|£ n+1. If w=e , the statement is true. If w¹ e , we can write w as w=aw’b, wÎ B. Thus |w’|£ n-1£ n. Thus |w’| is even. Thus |w|=|w’|+2 is even.

  2. Write a non-recursive definition for B.

B={anbn : n=0, 1, …}
  1. (25 pts) Prove that {a,b}* is countable.

Define 1-1, f: {a,b}* ® {0,1,2,…} as follows:

f(e )=0, f(a)=1, f(b)=2,

f(a n a n-1 …a 1)= f(a 1)+ f(a 2)2+ f(a 3)4+… f(a n)2n-1

To show f is 1-1, suppose f(a n a n-1 …a 1)= f(b m b m-1 …b 1).

Then (f(a n a n-1 …a 1)-1) mod 2=( f(b m b m-1 …b 1)-1) mod 2

Þ (a 1-1)= (b 1-1) Þ a 1= b 1. Now apply this argument inductively.

Let B=Image(f). Then f:{a,b}*® B is 1-1, onto. But B is a subset of {0,1,…}, which means B is countable, which means {a,b}* is countable.

4. (20 pts) Find a dfa equivalent to the nfa M=({s,1,2,3,4}, {a,b}, s, {1,2},

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

We construct the function d recursively as follows:

d | a b

------------------------

{s} {1,2,3} f

{1,2,3} {1,2} {1,4}

{1,2} f {1,4}

{1,4} f {s,1,4}

{s,1,4} {1,2,3} {s,1,4}

f f f

The states are listed in the column under d , the start state is {s}, the set of

accepting states is {{1,2,3}, {1,2}, {1,4}, {s,1,4}}

Draw a diagram of the resulting dfa.

  1. (10 pts) Given the dfa M=({s,1,2,3}, {a,b}, s, {3}, {((s,a),1), ((s,b),2),

((1,a),3), ((1,b),2), ((2,a),1), ((2,b),s), ((3,a),2), ((3,b),s)}, prove that each

of the strings below is or is not in L(M).
  1. ab3 d (s,abbb)= d (1,bbb)= d (2,bb)= d (s,b)=2Ï {3} Þ reject
  2. ba3 d (s,baaa)= d (2,aaa)= d (1,aa)= d (3,a)=2Ï {3} Þ reject

6. (15 pts) Prove that a* È bbb È bab* is a regular expression. Draw the diagram of an nfa whose language is the language of this regular expression.

a is a regular expression Þ a* is a regular expression.

b is a regular expression Þ bb is a regular expression Þ bbb is a regular

expression.

b is a regular expression Þ b* is a regular expression.

b, a, and b* are regular expressions Þ bab* is a regular expression.

Finally, a*, bbb, and bab* are regular expressions Þ a* È bbb È bab* is

a regular expression.