Assignment 3, Questions 3 and 4

Posted by gert_yes
Announcements Last Post
: Programming Students at UNISA School of Computing 06/19/2019 02:01PM
SoC Curricula 09/30/2017 01:08PM
Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
School of Computing Short Learning Programmes 11/24/2014 08:37AM
Unisa contact information 07/28/2011 01:28PM
 Assignment 3, Questions 3 and 4 June 09, 2008 07:14PM Registered: 12 years ago Posts: 94 Rating: 0
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.

Gert.
 Re: Assignment 3, Questions 3 and 4 June 12, 2008 12:33PM Registered: 14 years ago Posts: 92 Rating: 0
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.
 Re: Assignment 3, Questions 3 and 4 June 13, 2008 07:23AM Registered: 11 years ago Posts: 423 Rating: 0
Thanks.

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 Registered: 14 years ago Posts: 92 Rating: 0
I do not know why you say this. Refer to rule 4 on p. 125
 Re: Assignment 3, Questions 3 and 4 June 17, 2008 10:23AM Registered: 11 years ago Posts: 423 Rating: 0
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 Registered: 14 years ago Posts: 92 Rating: 0
Yes, this is one way of seeing it, refer to Cohen pp. 32, 33.
 Re: Assignment 3, Questions 3 and 4 July 08, 2008 12:30PM Registered: 11 years ago Posts: 423 Rating: 0
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.
Sorry, only registered users may post in this forum.