Re: Help Badly needed- FSA and ASCII stuff


On Mon, 27 Feb 2006, Willing 2 Learn wrote:

Hey, I'm trying to teach myself C++ and I came across 3 problems.

You mean, "I'm taking a class on C++ and I have a homework assignment"?
Because that's what it looks like. Nobody here is going to do your homework for you. But I'll give you some useful hints.


1) Devise a coding system to send CAPITAL LETTERS using the ASCII code.
Assume the lights will be ON when you start sending, and use OFF for
ZERO and ON for ONE.

You'll want to start by looking up the ASCII codes for the capital letters. Now: is there anything you need to add to that code to make
it work with "off" and "on" lights instead of 0 and 1 bits? (Yes. And
the assignment gives you its own hints, below.)

3. Write a regular expression and FSA to recognize your code.
HINT given: Consider the following issues:
* How does the received know the difference between a ONE data bit and
the ON normal state of the lights, that is, how does the receiver know
when you START and STOP sending?
* How does the receiver know how long a bit lasts, i.e., how does it
distinguish 1 from 11 from 111 ? In other words, if your code
contains a long string of zeros or ones, could the receiver lose count?

You might find the page
http://www.cacr.math.uwaterloo.ca/~dstinson/visual.html
to contain useful concepts. Big hint: If I were doing this assignment,
I'd use /three/ bits (on-off states of the light) to represent each /one/ bit of the original ASCII code. What might the third bit be for?


2) Write a program for an FSA to recognize the Regular Expression
01(00+11)*10.

Ask your instructor what the symbols * and + stand for. Then start by
writing an FSA to recognize "01". Then one for "00+11". Then one for
"(00+11)*10". Then write one to recognize the whole language.
Drawing diagrams something like this will also help:
http://www.zefhemel.com/upload/fsa1.png


3) Use C++ to implement a Non-deterministic Finite Automaton to
recognize a string consisting of the 8-bit ASCII codes for JAH

What is "JAH"? Anyway, for this project, an NDFA is just a FSA where instead of keeping track of one state, you keep track of a /set/ of states --- a set that can be as large as your total number of states. So, what tools does C++ give you to represent sets? :)

Part 3 is really a pretty big project, if you do it right. You should definitely talk to your instructor if you're having trouble making sense
of the specification.

HTH,
-Arthur
.