Computer Science Canada Help Desperatly needed on These Questions!! |
| Author: | bladeb2k [ Wed Aug 15, 2007 8:52 am ] |
| Post subject: | Help Desperatly needed on These Questions!! |
If you know anyone that can help me with these two computer science questions i'll be sooo grateful. 1) The input to a program is to be a series of binary numbers seperated by commas e.g. 101, 111, 11011. The number zero is always written as 0 (i.e 0000 is not acceptable) however 01, 00101 and so on are acceptable for non-zero numbers. Draw a deterministic finite state automaton which will accept the data described above. 2) The range of data to be accepted by the program has been extended to allow numbers to be grouped within parenthesis eg. 01,{01,0,{10,1,{0,1},{1}}},1 Design a Turing machine which will check for correctly formatted data. In this version the restriction of 0 being only represented by a single symbol need not be adhered to. The TM should check for correctly matched {and} but need not detect misplaced commas (as in, eg. {0,}). You should assume: i) the data is initially positioned on an otherwise blank tape (i.e. all spaces) with the TM's reading head above the first character. ii) All commas are legally placed but {and} may not be iii) the TM will end in one of the following states: VALID DATA TOO MANY '}' TOO MANY '{' with the obvious interpretation. |
|
| Author: | Nick [ Wed Aug 15, 2007 8:55 am ] |
| Post subject: | RE:Help Desperatly needed on These Questions!! |
u already posted this question... anyway by binary do u mean 01001100=76? or just the process of 0's and 1's in general? |
|
| Author: | bladeb2k [ Wed Aug 15, 2007 9:00 am ] |
| Post subject: | Re: Help Desperatly needed on These Questions!! |
By binary it means actual 01001100=76 etc. |
|
| Author: | Nick [ Wed Aug 15, 2007 9:01 am ] |
| Post subject: | RE:Help Desperatly needed on These Questions!! |
so would u then convert the number ur receiving into ASCII to create characters? |
|
| Author: | Aziz [ Wed Aug 15, 2007 9:11 am ] |
| Post subject: | RE:Help Desperatly needed on These Questions!! |
Post in the other thread in Turing forums. |
|
| Author: | PaulButler [ Wed Aug 15, 2007 9:17 am ] |
| Post subject: | RE:Help Desperatly needed on These Questions!! |
momop, he needs to design a finite state automation, not a program. The binary to decimal conversion is irrelevant. Look again at the problem. It simplifies to this: - Reject the series if it contains only 0s - Accept the series otherwise But if you don't understand deterministic finite state automations, that won't help you much. You must have a textbook or something? |
|
| Author: | bladeb2k [ Wed Aug 15, 2007 9:22 am ] |
| Post subject: | Re: Help Desperatly needed on These Questions!! |
I have a textbook but it's all jargon - it doesn't make sense. Does anyone know another forum or something where anyone would be able to help me |
|
| Author: | Nick [ Wed Aug 15, 2007 9:27 am ] |
| Post subject: | RE:Help Desperatly needed on These Questions!! |
when is this due? |
|
| Author: | Aziz [ Wed Aug 15, 2007 9:31 am ] |
| Post subject: | RE:Help Desperatly needed on These Questions!! |
Probably tomorrow - rofl. If the textbook is all jargon, it seems that you've missed more than just one class. Like I said, do some google searches and wikipedia reading. |
|
| Author: | bladeb2k [ Wed Aug 15, 2007 9:33 am ] |
| Post subject: | Re: Help Desperatly needed on These Questions!! |
it's due on monday, i'll try some searches now. |
|
| Author: | Nick [ Wed Aug 15, 2007 9:41 am ] |
| Post subject: | RE:Help Desperatly needed on These Questions!! |
well atleast u got time well i have no clue so good luck! |
|
| Author: | Dan [ Wed Aug 15, 2007 2:21 pm ] |
| Post subject: | RE:Help Desperatly needed on These Questions!! |
Moved to General Programming. |
|
| Author: | CodeMonkey2000 [ Wed Aug 15, 2007 4:31 pm ] |
| Post subject: | RE:Help Desperatly needed on These Questions!! |
What language are you doing this in? This doesn't sound that hard, as I've said before, it's just a simple string manipulation problem. |
|
| Author: | Cervantes [ Wed Aug 15, 2007 5:47 pm ] |
| Post subject: | RE:Help Desperatly needed on These Questions!! |
What should be the output if the input is "}{"? There aren't too many "{" and nor are there too many "}", but they are formatted incorrectly. |
|
| Author: | Aziz [ Wed Aug 15, 2007 10:14 pm ] |
| Post subject: | RE:Help Desperatly needed on These Questions!! |
Read his post in Turing Help. He's not programming ... |
|
| Author: | CodeMonkey2000 [ Wed Aug 15, 2007 11:19 pm ] |
| Post subject: | RE:Help Desperatly needed on These Questions!! |
It got deleted. |
|
| Author: | Aziz [ Thu Aug 16, 2007 8:48 am ] |
| Post subject: | RE:Help Desperatly needed on These Questions!! |
Yup. it's gone. No trash. That blows. Anyways, he basically said its an information technology course, and he missed the class on Turing machine. He said it has to be done on paper, and he hadn't been taught any programming languages. Also... the text book makes no sense to him. Thats all the info. I think he's SOL |
|
| Author: | OneOffDriveByPoster [ Thu Aug 16, 2007 12:58 pm ] | ||||
| Post subject: | Re: Help Desperatly needed on These Questions!! | ||||
Some badly drawn deterministic finite state automatons: Accept "0"
Accept any number of zeros (0 or more)
where ( ) is a state, (( )) is an accepting state, and there is an implicit error state; "v ^" is a looping arrow. Usually should be circles for states (double circle for accepting state) and labeled arrows for transitions. The start state is the one pointed to by the arrow from nowhere. As you can see, you can take a string and "walk" the arrows depending on what character you are on. If you get "stuck" or if you finish in a non-accepting state, the string is not accepted by the machine. If you end on an accepting state (but not if you are "stuck" in one), the machine accepts the string. Basically, you are being asked to produce one of these diagrams such that it will only accept strings of the form described by the assignment. |
|||||
| Author: | Aziz [ Thu Aug 16, 2007 1:19 pm ] |
| Post subject: | RE:Help Desperatly needed on These Questions!! |
*claps* Bravo |
|
| Author: | PaulButler [ Thu Aug 16, 2007 6:37 pm ] |
| Post subject: | RE:Help Desperatly needed on These Questions!! |
OneOff, I thought with a deterministic finite state automation you needed a line out of each state for each character that belongs to the language? If so, the language of your automations is {0} which doesn't make them very useful. |
|
| Author: | OneOffDriveByPoster [ Thu Aug 16, 2007 9:24 pm ] | ||||
| Post subject: | Re: RE:Help Desperatly needed on These Questions!! | ||||
PaulButler @ Thu Aug 16, 2007 6:37 pm wrote: OneOff, I thought with a deterministic finite state automation you needed a line out of each state for each character that belongs to the language? If so, the language of your automations is {0} which doesn't make them very useful.
Nope. Implicit transitions to the implicit error state were employed--very easy to transform if needed. But yes, the alphabet was {0}. I was just hoping to see if this was enough to help the OP. I guess I can pull up some exercise books to add a better example. May work on the TM example sometime. Edit: http://en.wikipedia.org/wiki/Deterministic_finite_state_machine has a proper picture. More examples then: All binary strings of even length:
All binary strings with at least two 1's:
The comma-separated lists in the transition labels have the obvious meaning. Edit: http://en.wikipedia.org/wiki/Turing_machine will help; search for "state transition" (no quotes). |
|||||
| Author: | PaulButler [ Fri Aug 17, 2007 10:45 am ] |
| Post subject: | RE:Help Desperatly needed on These Questions!! |
Cool, I didn't know about the implicit error state. |
|