Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

a5p3 - not23.dfa

412 views
Skip to first unread message

jason tran

unread,
Feb 5, 2012, 3:43:36 PM2/5/12
to
Hey, just to clarify, they mean not divisible by EITHER 2 or 3 (ie.
not divisible by 2 and not divisible by 3).

Ryan

unread,
Feb 5, 2012, 6:21:15 PM2/5/12
to
Yes

Kam

unread,
Feb 7, 2012, 12:20:52 AM2/7/12
to
On 2/5/2012 6:21 PM, Ryan wrote:
> Yes

Any hints on how to start this DFA? I ones I came up with sometimes
work, but there were a few cases where it failed.

Stephen Pisani

unread,
Feb 7, 2012, 9:37:49 AM2/7/12
to
The language consists of binary integers x such that

2 does not divide x
3 does not divide x

If you want to give yourself an idea of what numbers this includes you
can solve the system with the Chinese Remainder Theorem, but the actual
DFA is similar to what you did for A5P2 with an extra condition. You can
also try drawing the NFA first; one of the examples in Friday's tutorial
had a similar NFA to DFA conversion as this question.

If it's failing in a few cases then you probably don't have enough
states to cover all possibilities.

Kam

unread,
Feb 7, 2012, 2:17:59 PM2/7/12
to
On 2/7/2012 9:37 AM, Stephen Pisani wrote:
>>

Thanks for your suggestion. I was half way through the CRT but I got too
confused with congruences so I gave up on that approach and just made a
NFA of the solution and converted to DFA.
0 new messages