Peter Linz Exercise 2.1 question 8.a)

Question

A run in a string is a substring of length at least two,as long as possible and consisting entirely of same symbol.For instance the string abbbaab has a run 3 of b and run 2 for a.find DFAs for following languages on {a,b}

a)L={w : w contains no run of less than four}

 

b)L={W :every run of a is either 2 or 3}

 

how to draw dfa for this kind of questions?

Comments

@Shubham Sharma 2 in answer for problem 2.1.8(c) , why is it accepting strings with run length of  a's as 1, as the question has clearly mentioned that 'every run of a’s has length either two or three'. 

---

in the part (a ) of this question ,can’t we remove the 2 states after initial state and directly go to the next states means what is the use of these states?

and can anyone tell me how to insert an image here

---

but isn’t the string accepting strings of length less than 4 it is even accepting the empty string

Answer 1

1.  L={aaaa,bbbb,aaaaa,bbbbb,aaaabbbb,aaaabbbbaaaa,bbbbaaaabbbb,aaaaaaaabbbb,aaaaabbbbbaaaaa……...}