Author |
Topic: Discrete Maths (Read 417 times) |
|
kens
Junior Member
Posts: 59
|
 |
Discrete Maths
« on: Jul 24th, 2007, 2:11pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Discrete Maths
« Reply #1 on: Jul 24th, 2007, 3:17pm » |
Quote Modify
|
Concatenate two DFA, one which accepts all string (a.b)*, and one which accept all strings that are not aabb.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
kens
Junior Member
Posts: 59
|
|
Re: Discrete Maths
« Reply #2 on: Jul 24th, 2007, 3:35pm » |
Quote Modify
|
How to draw a DFA that does not accept aabb?
Should we define a dead state on reaching the 2nd b of aabb?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Discrete Maths
« Reply #3 on: Jul 24th, 2007, 3:42pm » |
Quote Modify
|
on Jul 24th, 2007, 3:35pm, 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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print