Question

Draw state diagram for following R.E. (a/b)abc(b*)
(a/b/c)*abab
aaa(c/b*)*

Answer 1

Answer:1. The following nondeterministic automaton accepts the set of strings in

{ a, b} * ending in aaa. Convert this automaton to an equivalent deterministic one using the subset construction. Show clearly which subset

of {s, t, 'It, v} corresponds to each state of the deterministic automaton.

Omit inaccessible states.

a,b

Q a - .. a

••

s t

2. The reverse of a string x, denoted rev x, is x written backwards.

Formally,

def

reVE = E,

def rev xa = a rev x.

For example, rev abbaaab = baaabba. For A ~ l:*, define

rev A ~ {rev x I x E A}.

For example, rev {a,ab,aab,aaab} = {a,ba,baa,baaa}. Show that for

any A ~ l:*, if A is regular, then so is rev A.

3. The Hamming distance between two bit strings x and y (notation:

H(x,'O)) is the number of places at which they differ. For example,

H(Ol1, 110) = 2. (If Ixl ::f. 1'01, then their Hamming distance is infinite.)

If x is a string and A is a set of strings, the Hamming distance between

x and A is the distance from x to the closest string in A:

H(x,A) ~ minH(x,'O).

ilEA

For any set A ~ {0,1}* and k ~ 0, define

Nk(A) ~ {x I H(x, A) 5 k},

Explanation: