Welcome! Log In Create A New Profile

Advanced

Assignment 3, Questions 3 and 4

Posted by gert_yes 
Announcements Last Post
Announcement : Programming Students at UNISA School of Computing 06/19/2019 02:01PM
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
Assignment 3, Questions 3 and 4
June 09, 2008 07:14PM
Hi All,

Could anyone tell me which part of Kleene's theorem we have to use for questions 3 and 4?

I was able to get an NFA with 3 states by trail and error using the techniques from Chapter 5, but I don't know if we have to use one of the parts of Kleene's theorem.

The same goes for question 4.

According to theorem 7 p.137 of Cohen there is a FA for every NFA that accepts the exact same language. That I get. In proof two of theorem 7 p.138 of Cohen there is something written on the fact that the algorithm for producing FA* form FA should be used, or so it looks.

Am I on the right track for these questions or am I barking up the wrong tree.

Thanks for your replies in advance,

Gert.
Re: Assignment 3, Questions 3 and 4
June 12, 2008 12:33PM
With Questions 3 and 4 your insight is tested because the states of the required NFA and FA must be less than the original FAs. There is no algorithm to do this.
avatar Re: Assignment 3, Questions 3 and 4
June 13, 2008 07:23AM
Thanks.

This explains the comments on assignment 02 about see simplified answers in solution letter.

Also I noticed that using Kleene's theorem from FA of 'b' to 'b*' generates an FA bb*. Is this right?

B
Re: Assignment 3, Questions 3 and 4
June 13, 2008 09:20AM
I do not know why you say this. Refer to rule 4 on p. 125
avatar Re: Assignment 3, Questions 3 and 4
June 17, 2008 10:23AM
Sorry. I left out the empty string. It generates (null)+bb*

So from experience, practice and insight will enable us to see this as b*?

Thanks
B
Re: Assignment 3, Questions 3 and 4
June 24, 2008 10:00AM
Yes, this is one way of seeing it, refer to Cohen pp. 32, 33.
avatar Re: Assignment 3, Questions 3 and 4
July 08, 2008 12:30PM
Now I see that the method used in chapter 11 of Cohen can determine if different regular expressions or FA's accept the same language. smile
Sorry, only registered users may post in this forum.

Click here to login