---

CS381 Fall 2001 – Homework 2

Prof Shai Ben-David

DUE: Friday, 9/21, 9:00 am

NOTE: EVERY claim you make should be supported by an explanation or a proof

1. Prove that if L₁,L₂ are regular languages, then so is: L₁\L₂={wÎL₁:wÏL₂}

2. Given a DFA, M=(Q,S,q₀,d,F) and p,qÎQ, let L(M,p,q)={w: (p,w)=q}. Prove/refute each of the following claims:

(i) For every M,p,q as above and every x,yÎS*, if xÎL(M,p,q) and yÎL(M,q,p) then xyÎL(M,p,p)

(ii) For every M,p,q as above and every x,y,zÎS*, if yzÎL(M,p,q) then there exist some rÎQ such that for every xÎL(M,r,r) and every iÎN, yxⁱzÎL(M,p,q).

3. Recall that a language is called “regular” if it is computable by some DFA.

(i) Prove that any intersection of finitely many regular languages is a regular language.

(ii) Prove that there exist a set W of regular languages so that the intersection of all languages in W is not regular.

(iii) BONUS: find a set W of regular languages such that W is infinite and yet the intersection of all the languages in W is an infinite regular language.

4. Find a set W consisting of infinitely many languages over {0,1} so that:

(i) Each language in W is infinite

(ii) Each language in W is regular (i.e. computable by some DFA)

(iii) For every pair of languages L_1,L₂ÎW, if L₁¹L₂ then L₁ÇL₂=F

5. Construct a DFA, M, such that L(M)=L(N) where N is the following NFA:

(here S={a,b,c})

6. Construct a NFA, M, over S={1,2,3,4,5} such that M has only 5 states and L(M)={w=s₁s₂ ... s_|w| : for all i<j<|w|, s_i£s_j} (that is, the numbers that are the letters in w appear in increasing order).

---