wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> Discrete Maths
        
(Message started by: kens on Jul 24^th, 2007, 2:11pm)

Title: Discrete Maths
Post by kens on Jul 24^th, 2007, 2:11pm

A Deterministic Finite Automaton (DFA) is to be drawn for language (a.b)* which does not accept aabb.

Please tell me how to approach this problem.

Title: Re: Discrete Maths
Post by towr on Jul 24^th, 2007, 3:17pm

Concatenate two DFA, one which accepts all string (a.b)*, and one which accept all strings that are not aabb.

Title: Re: Discrete Maths
Post by kens on Jul 24^th, 2007, 3:35pm

How to draw a DFA that does not accept aabb?

Should we define a dead state on reaching the 2nd b of aabb?

Title: Re: Discrete Maths
Post by towr on Jul 24^th, 2007, 3:42pm

on 07/24/07 at 15:35:36, kens wrote:

How to draw a DFA that does not accept aabb?

Should we define a dead state on reaching the 2nd b of aabb?

A reject state, yes. But if any other input follows we must accept. (aabba would be fine)